# Subsets
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/subsets)
Canonical: https://scaleengineer.com/dsa/problems/subsets
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Mastercard](https://scaleengineer.com/companies/mastercard), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Samsung](https://scaleengineer.com/companies/samsung), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Coupang](https://scaleengineer.com/companies/coupang), [Salesforce](https://scaleengineer.com/companies/salesforce), [Fiverr](https://scaleengineer.com/companies/fiverr)
---
## Problem
Given an integer array `nums` of **unique** elements, return _all possible_ _subsets_ _(the power set)_.

The solution set **must not** contain duplicate subsets. Return the solution in **any order**.

**Example 1:**

**Input:** nums = [1,2,3]
**Output:** [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

**Example 2:**

**Input:** nums = [0]
**Output:** [[],[0]]

**Constraints:**

* `1 <= nums.length <= 10`
* `-10 <= nums[i] <= 10`
* All the numbers of `nums` are **unique**.

# Approaches
## Iterative Approach (Cascading)
This approach builds the solution iteratively. It starts with an empty subset in the result list. Then, it iterates through each number in the input array. For each number, it goes through all the subsets currently in the result list, creates a new subset by adding the current number to each of them, and adds these new subsets to the result list.
**Time:** O(n * 2^n) · **Space:** O(n * 2^n)
**Pros:** - Intuitive and easy to understand.; - Avoids recursion, so there's no risk of stack overflow.
**Cons:** - Can be less performant due to the overhead of creating many new list objects and copying elements in each step.
### Explanation
The algorithm begins by initializing the result list with just the empty set. It then iterates through each number in the input `nums` array. In each iteration, it effectively doubles the number of subsets in the result list. It does this by iterating through the subsets that have been computed so far, and for each one, it creates a new subset that is a copy of the existing one plus the current number. These newly formed subsets are then added to the result list.

For example, with `nums = [1, 2]`: 
1. Start with `result = [[]]`.
2. Process `1`: Create a new subset `[1]` from `[]`. Add it. `result` is now `[[], [1]]`.
3. Process `2`: Create new subsets `[2]` (from `[]`) and `[1, 2]` (from `[1]`). Add them. `result` is now `[[], [1], [2], [1, 2]]`.

```java
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>()); // Start with the empty set

        for (int num : nums) {
            int currentSize = result.size();
            for (int i = 0; i < currentSize; i++) {
                // Create a new subset from an existing one and add the current number
                List<Integer> newSubset = new ArrayList<>(result.get(i));
                newSubset.add(num);
                result.add(newSubset);
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize a list of lists `result` and add an empty list to it.
- For each number `num` in the input array `nums`:
  - Get the current number of subsets in `result`.
  - Iterate through the existing subsets (from index 0 to the original size).
  - For each existing subset, create a new subset by copying it and adding `num`.
  - Add this new subset to the `result` list.
- Return `result`.

## Backtracking
This is a classic recursive approach to generate all combinations. We use a helper function that builds a subset. At each step, we have two choices for an element: either include it in the current subset or not. The backtracking algorithm explores all these possible choices to form all subsets.
**Time:** O(n * 2^n) · **Space:** O(n * 2^n)
**Pros:** - A standard and elegant pattern for solving many combinatorial problems.; - It is a very generalizable approach that can be adapted for similar problems like combinations and permutations.
**Cons:** - Recursion can have a higher overhead than iterative solutions.; - The concept of backtracking might be less intuitive for beginners.
### Explanation
The core of this approach is a recursive helper function, often called `backtrack`. This function is responsible for building the subsets. It takes the current position `start` in the `nums` array and the `currentSubset` being built as parameters.

At each call, we first add the current state of `currentSubset` to our final result list. This captures subsets of all possible lengths. Then, we loop from the `start` index to the end of the array. In each iteration of the loop, we 'choose' an element by adding it to `currentSubset`, then 'explore' further possibilities by making a recursive call with the next index (`i + 1`). After the recursive call returns, we 'unchoose' the element by removing it from `currentSubset`. This 'unchoosing' step is the backtracking part, which allows us to explore different branches of the solution space, such as subsets that do not include the current element but include subsequent ones.

```java
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(0, new ArrayList<>(), nums, result);
        return result;
    }

    private void backtrack(int start, List<Integer> currentSubset, int[] nums, List<List<Integer>> result) {
        // Add the current combination to the result list
        result.add(new ArrayList<>(currentSubset));

        for (int i = start; i < nums.length; i++) {
            // Include the element nums[i]
            currentSubset.add(nums[i]);
            // Explore subsets starting from the next element
            backtrack(i + 1, currentSubset, nums, result);
            // Backtrack: remove the element to explore other subsets
            currentSubset.remove(currentSubset.size() - 1);
        }
    }
}
```
### Algorithm
- Define a recursive function `backtrack(start, currentSubset, nums, result)`.
- In the main function, initialize an empty `result` list and call `backtrack(0, new ArrayList<>(), nums, result)`.
- Inside `backtrack`:
  - Add a copy of `currentSubset` to the `result` list.
  - Loop with an index `i` from `start` to the end of the `nums` array.
    - Add the element `nums[i]` to `currentSubset`.
    - Make a recursive call: `backtrack(i + 1, currentSubset, nums, result)`.
    - Remove the last element from `currentSubset` to backtrack.

## Bit Manipulation
This approach leverages the fact that for `n` elements, there are `2^n` possible subsets. Each subset can be represented by an `n`-bit integer (a bitmask). If the `j`-th bit is 1, the `j`-th element of the input array is included in the subset; otherwise, it's not.
**Time:** O(n * 2^n) · **Space:** O(n * 2^n)
**Pros:** - Very efficient in practice due to fast bitwise operations and an iterative structure.; - Conceptually clean and concise for those familiar with bit manipulation.; - Generates subsets in a predictable, lexicographically sorted order (based on the bitmask).
**Cons:** - The approach is limited by the size of standard integer types (e.g., `long` for up to `n=64`), though this is not an issue for the given constraints.; - Might be less intuitive if one is not comfortable with bit manipulation.
### Explanation
The key idea is to map each subset to a unique binary number. For an input array of size `n`, we can represent all `2^n` subsets using numbers from `0` to `2^n - 1`. Each of these numbers serves as a bitmask of length `n`.

We iterate from `i = 0` to `2^n - 1`. For each `i`, we construct a corresponding subset. We do this by iterating through the bits of `i` from `j = 0` to `n-1`. If the `j`-th bit of `i` is set to 1, it signifies that the element `nums[j]` should be included in the current subset. We can check the `j`-th bit using the bitwise operation `(i >> j) & 1`.

This method is very direct and avoids recursion. It systematically generates all subsets based on the binary representation of numbers.

```java
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        int numSubsets = 1 << n; // This is 2^n

        // Iterate from 0 to 2^n - 1
        for (int i = 0; i < numSubsets; i++) {
            List<Integer> currentSubset = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                // Check if the j-th bit in i is set
                if ((i >> j & 1) == 1) {
                    currentSubset.add(nums[j]);
                }
            }
            result.add(currentSubset);
        }
        return result;
    }
}
```
### Algorithm
- Let `n` be the length of `nums`.
- Calculate the total number of subsets, `numSubsets = 2^n`.
- Initialize an empty list of lists `result`.
- Loop with an integer `i` from `0` to `numSubsets - 1`.
  - This `i` will act as a bitmask.
  - Initialize an empty list `currentSubset`.
  - Loop with an integer `j` from `0` to `n - 1`.
    - Check if the `j`-th bit is set in `i` using `(i >> j & 1) == 1`.
    - If it is, add the element `nums[j]` to `currentSubset`.
  - After the inner loop, add `currentSubset` to `result`.
- Return `result`.

# Solutions
### Java

```java
class Solution {
private
  List<List<Integer>> ans = new ArrayList<>();
private
  List<Integer> t = new ArrayList<>();
private
  int[] nums;
public
  List<List<Integer>> subsets(int[] nums) {
    this.nums = nums;
    dfs(0);
    return ans;
  }
private
  void dfs(int i) {
    if (i == nums.length) {
      ans.add(new ArrayList<>(t));
      return;
    }
    dfs(i + 1);
    t.add(nums[i]);
    dfs(i + 1);
    t.remove(t.size() - 1);
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> subsets(vector<int> &nums) {
    vector<vector<int>> ans;
    vector<int> t;
    function<void(int)> dfs = [&](int i) -> void {
      if (i == nums.size()) {
        ans.push_back(t);
        return;
      }
      dfs(i + 1);
      t.push_back(nums[i]);
      dfs(i + 1);
      t.pop_back();
    };
    dfs(0);
    return ans;
  }
};

```

### Python

```python
from typing import List class Solution : # bfs def subsets ( self , nums : List [ int ]) -> List [ List [ int ]]: if not nums : return [[]] nums . sort () # sort() not necessary if no duplicates result = [[]] for num in nums : result += [ subset + [ num ] for subset in result ] return result class Solution : # dfs def subsets ( self , nums : List [ int ]) -> List [ List [ int ]]: def dfs ( u , t ): ans . append ( t [:]) # or, t.copy() for i in range ( u , len ( nums )): t . append ( nums [ i ]) dfs ( i + 1 , t ) t . pop () ans = [] nums . sort () # sort() not necessary if no duplicates dfs ( 0 , []) return ans class Solution : # dfs, just pass down the final path def subsets ( self , nums : List [ int ]) -> List [ List [ int ]]: def dfs ( nums , index , path , ans ): ans . append ( path ) [ dfs ( nums , i + 1 , path + [ nums [ i ]], ans ) for i in range ( index , len ( nums ))] ans = [] dfs ( nums , 0 , [], ans ) return ans class Solution : # dfs, but running slower, since need to reference from parent method for 'nums' and 'ans' def subsets ( self , nums : List [ int ]) -> List [ List [ int ]]: def dfs ( index , path ): ans . append ( path ) [ dfs ( i + 1 , path + [ nums [ i ]]) for i in range ( index , len ( nums ))] ans = [] dfs ( 0 , []) return ans
```