Table of contents
1.
Introduction
2.
Solution using backtracking and recursion
2.1.
Algorithm for the solution
2.2.
Implementation of the solution(C++)
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is backtracking?
3.2.
Why is stack used for backtracking?
3.3.
Is backtracking always recursive?
3.4.
What is the difference between DFS and backtracking?
3.5.
How are greedy algorithms different from backtracking?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Sum of the Combination of Numbers | Part-1

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Bactracking and Recursion

Introduction

In this blog, we will discuss a very popular programming problem. We are given a set of numbers, and we need to find all the combinations of numbers such that the sum of the combination of numbers is equal to a given number.

Now, there are two variations of this problem-

In the first variant, we have an array of numbers, and we can use any number, any number of times. In the second variant of the problem, we can only use the numbers present in the given set. So in this blog, we will discuss the solution to the first case where we can use any number from any number of times. And the solution for the second variant is discussed in this blog. 

So let’s move on to a brief overview of the problem. It states that we are given an array of numbers out of which we can use any number, any number of times. Now, we are given a number, and we have to find all possible combinations of the numbers in the array such that the sum of the combination is equal to the given number.

Solution using backtracking and recursion

Even though there could be numerous solutions, we will learn about the solution based on recursion and backtracking. We will start with sorting the array of numbers in increasing order, and then we will remove any duplicates from the array. Now, we will be using backtracking and recursion, and whenever we add a number to the combination, we subtract its value from the given sum. If this value of sum becomes 0 at any point, the combination is added to the result. If it is negative, we ignore the combination. If it is positive, we continue adding new numbers and checking the value of the sum once we had traversed through all the possible combinations of the numbers in the array and pushed all combinations into the result array when the sum of combinations was 0. Then we print the result array.

Algorithm for the solution

  • Take the array of numbers and the sum value as user input.
  • Sort the array in increasing order.
  • Now we use backtracking and recursion to find the combinations with the given number. Whenever we add a number to combinations, we subtract it from the sum of the current combination. 
  • We choose the next step based on the value of the current sum of the combination-
    • -If it is zero, we add the combination to the result.
    • -If it is less than zero, we ignore the combination.
    • -If it is more than zero, we move on to the next number.

Implementation of the solution(C++)

#include <bits/stdc++.h>

using namespace std;

//Function to find the combinations.

void getnum( vector<int>&arr, int sum, vector< vector< int>>& result, vector< int>& temparr, int x)

{

    //When the sum of the combination is equal to the given value.

    if(sum==0)

    {

        result.push_back(temparr);

        return;

    }

    //Making recursive calls, when the sum of combination is

    //lesser than the given value.

    while(x< arr.size() && sum-arr[x]>=0)

    {

        //Adding the number to the combination.

        temparr.push_back(arr[x]);

        //make recursive calls for next number.

        getnum(arr, sum - arr[x], result, temparr, x);

        x++;

        // removing last element for backtracking.

        temparr.pop_back();

    }

}

//Function to find all the combinations with the given sum.

vector< vector< int>> sumofcombination(vector< int>& arr, int sum)

{

    //Sorting the array.

    sort(arr.begin(), arr.end());

    //Erasing the duplicates.

    arr.erase(unique(arr.begin(), arr.end()), arr.end());

    //Array to store the sum of combination.

    vector< int> temparr;

    //Array to store all the combinations.

    vector<vector< int>> result;

    //Recursive call to function which will check if a number

    //should be added to the combination or not.

    getnum(arr, sum, result, temparr, 0);

    return 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<vector< int> > result = sumofcombination(arr, sum);

    //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 <<"} ";

        }

    }

}
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 1 1 1 1 1 1 1 1 1 } {1 1 1 1 1 1 1 3 } {1 1 1 1 1 1 4 } {1 1 1 1 3 3 } {1 1 1 1 6 } {1 1 1 3 4 } {1 1 4 4 } {1 3 3 3 } {1 3 6 } {3 3 4 } {4 6 }

Complexity Analysis

The time complexity of the above approach is- O(N*sum), where N is the number of elements in the array.

The space complexity of the above approach is- O(N), where N is the number of elements in the array.

Check out this problem - Two Sum Problem

Frequently Asked Questions

What is backtracking?

Backtracking is a problem-solving approach in which we try to build the complete solution one step at a time by checking every candidate on given constraints for a possible solution. It abandons a candidate if it could not be a part of the solution. 

Why is stack used for backtracking?

Since we need to find all the possible combinations of the candidates, we use a stack to keep track of the candidates used for the combinations efficiently.

Is backtracking always recursive?

No, backtracking is generally implemented using recursion, but it can be implemented without using recursion.

What is the difference between DFS and backtracking?

DFS is an algorithm generally used for tree data structure, it shares the core concept of backtracking but is limited in application to the trees, whereas backtracking is a method of problem-solving in which we build a solution to the problem by finding one step of the solution at a time and discarding the scenarios which won’t be a part of the result.

How are greedy algorithms different from backtracking?

In backtracking, we make a recursive call to all available options after every step, but in the case of the greedy algorithm, we make a recursive call only to the best available option after each step.

Conclusion

In this blog, we learned how to find all the combinations from a given array of numbers so that the sum of the combinations is equal to a given number. We are allowed to use any number from the array any number of times. -

  • We learned about the recursion and backtracking-based solution to this problem. We started with sorting the number in the array then removing any duplicates present in the array. We use the given value to keep track of the sum of the current combination of the numbers, and whenever any new number is added to the combination, we decrease the value of the sum by that number. 
  • Then we start with making different combinations of the numbers in the array, using backtracking. If the sum of a combination becomes zero, we push that combination into the result array. If the sum goes less than zero, we ignore the combination. If the sum is greater than zero, we continue backtracking as it is. Once we have been through all the combinations, we print the combinations stored in the result array.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Live masterclass