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.
7.
Key Takeaways
Last Updated: Mar 27, 2024

# Subsets

Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## 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.

## 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

OUTPUT

## 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)

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!

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems