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.
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
123 12 13 1 23 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
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.
38+ registered 