Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Subsets 
2.1.
Problem Statement
2.2.
Example and Explanation
3.
Approach
4.
C++ implementation
5.
Complexities
5.1.
Time Complexity
5.2.
Space Complexity
6.
Frequently Asked Questions
7.
Key Takeaways
Last Updated: Mar 27, 2024

Subsets

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 Coding Ninjas Studio  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.

Check out this problem - Minimum Coin Change Problem 

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

Happy Coding!

Previous article
Objective of The Knapsack Problem
Next article
Coin Change: Minimum Number Of Coins
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass