« Return subset of an array recursively

Problem

Given an integer array (of length n), find and return all the subsets of input array. 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 : Size of array

Line 2 : Array elements (separated by space)

Sample Input:

3

15 20 12

Sample Output:

[] (this just represents an empty array, don't worry about the square brackets)

12

20

20 12

15

15 12

15 20

15 20 12

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 subset(int input[], int n, int output[][20])
15{
16    if (n == 0)
17    {
18        output[0][0] = 0;
19        return 1;
20    }
21    int outputSize = subset(input + 1, n - 1, output);
22    for (int i = 0; i < outputSize; i++)
23    {
24        for (int j = 1; j <= output[i][0]; j++)
25        {
26            output[i + outputSize][j + 1] = output[i][j];
27        }
28        output[i + outputSize][0] = output[i][0] + 1;
29        output[i + outputSize][1] = input[0];
30    }
31    return (2 * outputSize);
32}
33int main()
34{
35    int input[20], length, output[35000][20];
36    cin >> length;
37    for (int i = 0; i < length; i++)
38    {
39        cin >> input[i];
40    }
41
42    int size = subset(input, length, output);
43
44    for (int i = 0; i < size; i++)
45    {
46        for (int j = 1; j <= output[i][0]; j++)
47        {
48            cout << output[i][j] << " ";
49        }
50        cout << endl;
51    }
52    return 0;
53}