« Print subsets of an array recursively

Problem

Given an integer array (of length n), find and print 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. Just print the subsets in different lines.

Input format :

Line 1 : Integer n, Size of array

Line 2 : Array elements (separated by space)

Constraints :

1 <= n <= 15

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