TITLE:-Return subsets sum to K
PROBLEM:-Given an array A of size n and an integer K, return all subsets of A which sum to K.
Subsets are of length varying from 0 to n, that contain elements of the array. But the order of elements should remain same as in the input array.
Note : The order of subsets are not important.
Line 1 : Integer n, Size of input array
Line 2 : Array elements separated by space
Line 3 : K
Constraints :
1 <= n <= 20
9
5 12 3 17 1 18 15 3 17
6
Sample Output :
3 3
5 1
SOLUTION:-
#include <iostream>
using namespace std;
int subsetSumToK(int input[], int n, int output[][50], int k) {
// Write your code here
if(n==0)
{
if(k==0)
{
output[0][0]=0;
return 1;
}
else
return 0;
}
int o1[1000][50],o2[1000][50];
int s1=subsetSumToK(input+1,n-1,o1,k-input[0]);
int s2=subsetSumToK(input+1,n-1,o2,k);
for(int i=0;i<s1;i++)
{
output[i][0]=o1[i][0]+1;
output[i][1]=input[0];
for(int j=0;j<o1[i][0];j++)
{
output[i][j+2]=o1[i][j+1];
}
}
for(int p=0;p<s2;p++)
{
output[p+s1][0]=o2[p][0];
for(int j1=0;j1<o2[p][0];j1++)
{
output[p+s1][j1+1]=o2[p][j1+1];
}
}
return (s1+s2);
}
int main() {
int input[20],length, output[10000][50], k;
cin >> length;
for(int i=0; i < length; i++)
cin >> input[i];
cin >> k;
int size = subsetSumToK(input, length, output, k);
for( int i = 0; i < size; i++) {
for( int j = 1; j <= output[i][0]; j++) {
cout << output[i][j] << " ";
}
cout << endl;
}
}