# Subsets

**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 stepsubsetHelper(nums, pos+1, curr, result); } vector<vector<int> > subsets(vector<int> &nums) { vector<vector<int>> result; //2D vector containing all the subsetsvector<int> curr; //1D vector containing the current subsetsubsetHelper(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(2
^{n}) - The time utilized within each recursive call is O(n).
- Thus, the overall time complexity is:

**T(n) = O(n * 2 ^{n})**

**Space Complexity**

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

**Space Complexity =** **O(n * 2 ^{n})**

**Frequently Asked Questions**

- How many unique subsets can we form from an array of n elements?

An array of n elements can form 2^{n}number of subsets. In the example given above, our input array is of size 3. So there are 2^{3}= 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!

Comments

## No comments yet

## Be the first to share what you think