New update is available. Click here to update.

Last Updated: 23 Jul, 2021

Difficulty: Easy

```
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows
The first line of each test case contains a single integers ‘N’ denoting the length of the array.
The second line of each test case contains ‘N’ integers denoting the array elements.
```

```
For each test case print each subset in a separate line.
The subsets can be print in any order.
Output for each test case will be printed in a separate line.
```

```
1 <= T <= 10
1 <= N <= 10
10^-9 <= arr[i] <= 10^9
Time limit: 1 sec
```

One of the standard and useful method of finding the power set is through bit-masking.

Consider a number with **N**-bits in its binary representation, if we consider that the state of **i ^{th}** bit depicts whether the

Now we can simply iterate from **1** to **2 ^{n}-1**, each number in this iteration will define a subset uniquely. To generate the subset just check for the bits that are ON in binary representation on the number, and for each ON bit, we will simply include an array element corresponding to its position.

Remember to not include an empty subset in the final answer.

The steps are as follows :

- Declare a 2-D container
**ans**to store all the subsets - Run a for loop for
**num**from**1**to**2^N -1** - Run inner for loop for
**i**from**0**to**N-1** - If the
**i**^{th}^{ }bit in**num**has value equal to**1**then include**i**element of the array in the current subset.^{th} - Push each subset generated into
**ans** - Finally, sort and print each container inside
**ans**in a separate line

Each element has 2 choices, it can either be included or excluded.

Using backtracking we can create all the possible subsets, we can add the current element to the temporary array and make a recursive call for the next element, when the function call returns we remove the current element from the temporary array and again make a recursive call for the next element (standard backtracking approach).

Each time we reach the end of the array, we will add the temporary array to the answer.

The steps are as follows :

- Initialize a 2D vector
**ans**to store all the subsets - Initialize a vector
**temp**to store the current subset - Create a recursive function
**SubsetFinder**which takes the following parameters:**idx**to store current index,**temp**vector to store current subset,**ans**2D vector to store all subsets,**arr**vector that is the input vector. - The initial call is made with
**idx**equal to**0**, empty**temp**vector, empty**ans**2D vector, given**arr**input vector - In
**SubsetFinder**we add the**idx**element to^{th}**temp**vector and recursively call**SubsetFinder**with**idx+1** - When a function call is returned, we remove the
**idx**^{th}^{ }element from**temp**, and again recursively call**SubsetFinder**with**idx+1** - If the value of
**idx**is equal to size of the input array, add**temp**to**ans** - Finally, sort and print each container inside
**ans**in a separate line

SIMILAR PROBLEMS

Prime Digit Sum

Posted: 17 Apr, 2022

Difficulty: Hard

Prime Digit Sum

Posted: 17 Apr, 2022

Difficulty: Hard

Mario And His Princess

Posted: 12 May, 2022

Difficulty: Moderate

Combination Sum III

Posted: 25 May, 2022

Difficulty: Moderate

Combination Sum III

Posted: 25 May, 2022

Difficulty: Moderate

Combination Sum III

Posted: 25 May, 2022

Difficulty: Moderate

Generate All Strings

Posted: 9 Jul, 2022

Difficulty: Moderate

8-Queen Problem

Posted: 19 Dec, 2022

Difficulty: Easy

Popular Interview Problems: