Sum of the combination of numbers | Part-2

Introduction

This blog discusses the solution to a very popular programming problem. We need to find all the combinations of numbers from a given set of numbers, such that the sum of the combination of numbers is equal to a given number.

In the previous blog on the sum of the combination of numbers, we learned the solution to the first variant of this problem, in which we can use any number, any number of times to make the combinations of the numbers. But, In this blog, we will discuss the second variant of the problem, in which we can only use the numbers present in the given set.

So let's again start with a brief overview of the problem. It states that we have an array of numbers. And, we also have a number. Now, we need to find all possible combinations of the numbers in the array such that the sum of the combination is equal to the given number. Remember that we can only use the numbers in the array and can't make duplicates of them as we did in the last blog.

See, Sum of the Combination of Numbers Part I

Solution using backtracking and recursion

The solution for this problem is very similar to the solution for a similar case of the problem in which we were allowed to repeat the elements any number of times. Still, in this case, we only sort the array and then use backtracking and Recursion to find all the unique combinations. We keep track of the current combination and push it into the result array if the sum equals the given value. If the sum is greater than the given value, we abandon the combination, and if it is lesser than the given value, we make a recursive call to get the next number in the combination. Finally, we print all the combinations from the result vector.

Algorithm for the solution

• Take the array of numbers and the sum value as user input.
• Sort the array in non-decreasing order.
• Now declare a two-dimensional vector that will store all combinations with a sum equal to the given value. And call the function to find all such combinations.
• We choose the next step based on the value of the current sum of the combination-
  • -If it is equal to the given value, we add the combination to the result.
  • -If it is more than the given value, we ignore the combination.
  • -If it is less than the given value, we move on to the next number.

Implementation of the solution in C++

#include <bits/stdc++.h>
using namespace std;
//Function to get all combination with sum equal to given value.
void getcombination(int x, int currsum, int sum,
                        vector<int>& currcombn,
                        vector<int>& arr,vector<vector< int> > &result)
{
    //To store the combination with sum equal to the given value.
    //For the combination with sum equal to the given value.
    if (currsum == sum)
    {
        //Store the combination in the result array.
        result.push_back(currcombn);
        return;
    }
    //For other combinations.
    for (int i = x; i < arr.size(); i++)
    {
        //If sum of the combination is greater than the given
        //value, ignore it.
        if (currsum + arr[i] > sum)
            continue;
        //To ignore the repetitive combinations
        if (i > x and arr[i] == arr[i - 1])
            continue;
        //If sum of the combination is smaller than the given
        //value, continue to find more combinations.
        currcombn.push_back(arr[i]);
        //Make recursive calls to find more combinations.
        getcombination(i + 1, currsum + arr[i], sum, currcombn,    arr,result);
        //Popping the last element for backtracking.
        currcombn.pop_back();
    }
}
//To find all the combination.
void findcombination(vector<int> arr, int sum,vector<vector<int>> &result)
{
    //To sort the array.
    sort(arr.begin(), arr.end());
    //To store the current combination.
    vector<int> currcombn;
    //Function call.
    getcombination(0, 0, sum, currcombn, arr,result);
}
//Driver function.
int main()
{
    vector< int> arr;
    int n;
    cout<<"No. of elements in the array-";
    cin>>n;
    cout<<"Enter the array elements-";
    for(int i=0;i<n;i++)
    {
        int a;
        cin>>a;
        arr.push_back(a);
    }
    int sum;
    cout<<"Enter the value of sum-";
    cin>>sum;
    //Vector to store all the combinations.
    vector<vector< int> > result;
    findcombination(arr, sum, result);
    //When there are no combinations.
    if (result.size() == 0)
    {
        cout<<"Empty";
        return 0;
    }
    // To print all the combination.
    for(int i=0;i<result.size();i++)
    {
        if(result[i].size()>0)
        {
            cout <<"{ ";
            for(int j=0;j<result[i].size();j++)
            {
                cout<< result[i][j]<<" ";
            }
            cout <<"}";
            cout<<endl;
        }
    }
}

You can also try this code with Online C++ Compiler

Run Code

Input

4
1 3 4 6
10

Output

No. of elements in the array-
Enter the array elements-
Enter the value of sum-
{1 3 6 } 
{4 6 }

Complexity Analysis

Time Complexity:  Overall complexity if O(2^N) because our algorithm will find all possible combinations in O(2^n) and for sorting it will take O(N log N), So overall complexity is O(2^N) + O(N log N) is equal to O(2^N).

Space Complexity: We use the variable currcombn to keep track of the current combination we build, which requires O(n) extra space.

Check out this problem - Check If A String Is Palindrome

Must Read Recursion in Data Structure