Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Solution using backtracking and recursion
2.1.
Algorithm for the solution
2.2.
Implementation of the solution in C++
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is recursion?
3.2.
What are some real-life examples of recursion?
3.3.
How can you find all the combinations of elements in an array of numbers, such that their sum is equal to a given number, given that we can use any number for any number of times?
3.4.
Which data structure works best for recursion?
3.5.
Why does a recursion-based solution generally have a higher space complexity than an iteration-based solution?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Sum of the combination of numbers | Part-2

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Bactracking and Recursion

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

 

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is recursion?

Recursion is a programming technique in which a process repeats itself until it meets specific criteria known as the base case of recursion.

What are some real-life examples of recursion?

Real-life examples of recursion include the Fibonacci series, in which each term is the sum of its last three terms.

How can you find all the combinations of elements in an array of numbers, such that their sum is equal to a given number, given that we can use any number for any number of times?

To find all the combinations of elements in an array of numbers, such that their sum is equal to a given number, given that we can use any number for any number of times, we use backtracking by recursion for this purpose. We first sort the array then remove any duplicates in it. Then we find all the possible combinations of its elements by backtracking and storing those combinations whose sum is equal to the given number. Then we print this array to print the results.

Which data structure works best for recursion?

Generally, stacks are used to implement recursion in different programming languages.

Why does a recursion-based solution generally have a higher space complexity than an iteration-based solution?

A recursion-based solution generally has a higher space complexity than the iteration-based solution because of the function call stack required, which increases the memory usage in a recursive solution. In contrast, there is no such thing in the case of an iterative solution.

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. But, we are not allowed to create duplicates of the elements in the array. We use a Backtracking and Recursion-based solution for this problem.

We started with sorting the number in the array and then finding all the combinations of the numbers using Recursion. For this, we keep track of the sum of the current combination. If the sum of the current combination is equal to the given value, we push it into the result array. If it is more than the given value, we abandon the combination. If it is less than the given value, we move to the next number for the combination. Once we have been through all the combinations, we print the result array containing all the required combinations

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.

Cheers!

Previous article
Sum of the Combination of Numbers | Part-1
Next article
Fibonacci Using Recursion
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass