Print all possible subsets of a given array

Companies:
  • Amazon Interview Questions
  • Apple Interview Questions
  • Bloomberg Interview Questions
  • ByteDance Interview Questions
  • Facebook Interview Questions
  • Google Interview Questions

Problem Statement

Find all the subsets of a given set.

Sample Test Cases

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Problem Solution

We will use the backtracking approach to solve this problem. Why backtracking? because backtracking technique is designed to generate every possible solution once.

So the Approach is that if we have N number of elements inside an array, we have exactly two choices for each of them, either we include that element in our subset or we do not include it.

 The take or not take strategy builds a binary tree of choices returning only the leaves for each combination resulting in the power-set of the entire array .

Complexity Analysis

Here we are generating every subset using recursion. The total number of subsets of a given set of size n = 2^n.

Time Complexity :  O( 2^n) For every index i two recursive case originates, So Time Complexity is O(2^n).

Space Complexity :  O(n 2^n)  We need to take into account the memory that is allocated by the algorithm not only on the stack but also on the heap. Each of the generated subsets is being stored in the subsets list, which will eventually contain 2n sets, each of size somewhere between 0 and n, so the space complexity is O(n 2^n).

Code Implementation

#include <bits/stdc++.h>
using namespace std;


void subsetsUtil(vector<int>& A, vector<vector<int> >& res,
                 vector<int>& subset, int index)
{
    res.push_back(subset);
    for (int i = index; i < A.size(); i++) {


        subset.push_back(A[i]);
        subsetsUtil(A, res, subset, i + 1);
        subset.pop_back();
    }

    return;
}

vector<vector<int> > subsets(vector<int>& A)
{
    vector<int> subset;
    vector<vector<int> > res;

    int index = 0;
    subsetsUtil(A, res, subset, index);

    return res;
}

int main()
{
    vector<int> array = { 1, 2, 3 };
    vector<vector<int> > res = subsets(array);


    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++)
            cout << res[i][j] << " ";
        cout << endl;
    }

    return 0;
}

 

Scroll to Top