Subsets

Aditya Narayan Joardar
Last Updated: May 13, 2022

Introduction

In this article, we will discuss the subsets problem. It has been asked in many famous competitive coding platforms. The subsets problem is considered an easy example in the backtracking paradigm.

The solution provided in this article uses the concepts of backtracking. Readers with no prior knowledge of backtracking may refer to this article: Backtracking

Subsets 

This article will discuss the subsets problem, some examples, and finally, the solution code. So, without any further ado, let’s begin.

Problem Statement

Given an integer array of unique elements, return all the possible subsets. The solution must not contain duplicate subsets. The order of the solution can be of any order.

Example and Explanation

INPUT 

nums = {1, 2, 3}

OUTPUT

{1, 2, 3}

{1, 2}

{1, 3}

{1}

{2, 3}

{2}

{3}

{}

From the given input and the output obtained, we can see that we are supposed to create all the possible subsets from the given input array. Since a blank/null array is also a valid subset, we print it.

For solving the subsets problem, we need to understand the use of backtracking. We have two options to choose from at any given point- either add an element to our list or discard it. For this, we make the recursive call twice. Once after taking the element and once after discarding the element.

Approach

To solve the Subsets problem, we follow the below-mentioned steps.

  • Create a 2D vector, result, to store all the possible subsets.
  • Create a 1D vector, curr, to store the current subset.
  • Call the helper function and pass the input vector, position pointer, the temporary current vector, and the final resultant vector. Here we send 0 as the position pointer because we want all the elements in the nums vector.
  • Our main recursive function is subsetHelper(). It takes four arguments- nums (the input integer vector), pos (the position pointer from which elements need to be inserted), curr (the temporary integer vector), result (the 2D resultant vector that will store all the subsets). We use call-by-reference on the result vector so that we can directly insert elements to it.
  • Our base case is when our position pointer points to nums.size(). When all the elements have been traversed, and the pointer points to the end of the vector. In this case, we just push the current vector, curr, into our resultant vector result and exit the recursion function.
  • If we have not reached the last element, then we have two options to choose from. Either add the element to our subset or discard it.
  • To add the element, we push the element at position pos in curr and call recursion at pos+1.
  • To discard the element, we pop the last element and call recursion at pos+1.

 

So by following our approach, the filling of the resultant vector will look like this-

First, the resultant vector contains null. We choose to insert elements 1, 2, 3 one after the other. Once they have been added, our curr contains {1, 2, 3} and the value of pos is 3. So, we add this subset to our resultant vector. We then decided to discard 3, so we pop the last element, that is 3, and call recursion on {1,2} which gradually gets added to our resultant vector. We do this until we are left with the null set, which is also a valid subset. 

Once all the recursive calls have been made, our resultant vector result stores all the subsets formed by the input matrix nums. In the main function, we call the respective function and then print the solution vector.

Before heading to the solution code, you can try the problem yourself on our CodeStudio  by clicking here: Print All Subsets

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
      
    void subsetHelper(vector<int> &nums,int pos, vector<int > curr, vector<vector<int>> &result){
        if(pos == nums.size()){
            result.push_back(curr);
            return;
        }

        curr.push_back(nums[pos]);
        subsetHelper(nums, pos+1, curr, result);
        curr.pop_back();        //backtracking step
        subsetHelper(nums, pos+1, curr, result);
    }

    vector<vector<int> > subsets(vector<int> &nums) {
        vector<vector<int>> result;     //2D vector containing all the subsets
        vector<int> curr;               //1D vector containing the current subset
        subsetHelper(nums, 0, curr, result);
        return result;
    }
};

int main(){
    Solution s;
    vector<int> nums {1,2,3};
  
    vector<vector<int> > result = s.subsets(nums);
  
    int i, j;
    for(i=0; i<result.size(); i++){
        vector<int> subset = result[i];
        for(j=0; j<subset.size(); j++){
            cout << subset.at(j) << " ";
        }
      
        cout << endl;
    }
}

OUTPUT

1 2 3
1 2
1 3
1
2 3
2
3

 

Complexities

Time Complexity

In the given solution, we generate all the subsets and then copy them into our output list.

  • The time utilized on each recursive call is T(n) = T(n-1) + T(n-2) + …. + T(1) + T(0). This results in T(n) = O(2n)
  • The time utilized within each recursive call is O(n).
  • Thus, the overall time complexity is:

T(n) = O(n * 2n) 

Space Complexity

In the given solution, we create a vector of vectors to store all the resultant subsets. Thus, 

Space Complexity = O(n * 2n)

Frequently Asked Questions

  1. How many unique subsets can we form from an array of n elements?
    An array of n elements can form 2n number of subsets. In the example given above, our input array is of size 3. So there are 23 = 8 possible subsets. 

Key Takeaways

To summarize the article, we thoroughly discussed the subsets problem. We saw the problem statement, a few examples and explanations, the approach to use, the solution code, the output generated, and the time and space complexities.

Want to ace the coding rounds of big tech companies? Try our Attempt Unlimited Online Mock Test Series to start your preparation.

Kick start your coding journey by practicing various coding problems on CodeStudio - The best platform to prepare for coding interviews
 

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think