« Return subsets sum to K recursively

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

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14int subsetSumToK(int arr[], int n, int output[][50], int k)
15{
16    if (n == 0)
17    {
18        if (k == 0)
19        {
20            output[0][0] = 0;
21            return 1;
22        }
23        else
24        {
25            return 0;
26        }
27    }
28    if (k == 0)
29    {
30        output[0][0] = 0;
31        return 1;
32    }
33    else if (k < 0)
34    {
35        return 0;
36    }
37
38    int output1[1000][50];
39    int size1 = subsetSumToK(arr + 1, n - 1, output1, k - arr[0]);
40
41    int output2[1000][50];
42    int size2 = subsetSumToK(arr + 1, n - 1, output2, k);
43
44    int i, j;
45
46    for (i = 0; i < size1; i++)
47    {
48        output[i][0] = output1[i][0] + 1;
49        output[i][1] = arr[0];
50    }
51
52    for (i = 0; i < size1; i++)
53    {
54        for (j = 1; j <= output1[i][0]; j++)
55        {
56            output[i][j + 1] = output1[i][j];
57        }
58    }
59
60    for (i = 0; i < size2; i++)
61    {
62        for (j = 0; j <= output2[i][0]; j++)
63        {
64            output[i + size1][j] = output2[i][j];
65        }
66    }
67
68    return size1 + size2;
69}
70
71int main()
72{
73    int input[20], length, output[10000][50], k;
74    cin >> length;
75    for (int i = 0; i < length; i++)
76    {
77        cin >> input[i];
78    }
79
80    cin >> k;
81
82    int size = subsetSumToK(input, length, output, k);
83
84    for (int i = 0; i < size; i++)
85    {
86        for (int j = 1; j <= output[i][0]; j++)
87        {
88            cout << output[i][j] << " ";
89        }
90        cout << endl;
91    }
92    return 0;
93}