Given an array A of size n and an integer K, return all subsets of A which sum to K.

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.

Input format :

Line 1 : Integer n, Size of input array
Line 2 : Array elements separated by space
Line 3 : K 

Constraints :

1 <= n <= 20

Sample Input :

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




• Tweet
• Share
• Share
• Share
• Share

About Admin MC3

This is dummy text. It is not meant to be read. Accordingly, it is difficult to figure out when to end it. But then, this is dummy text. It is not meant to be read. Period.

Related Post