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