78. Subsets - Explanation

Description

Given an array nums of unique integers, return all possible subsets of nums.

The solution set must not contain duplicate subsets. You may 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 = [7]

Output: [[],[7]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n * (2^n)) time and O(n) space, where n is the size of the input array.

Hint 1

It is straightforward that if the array is empty we return an empty array. When we have an array [1] which is of size 1, we have two subsets, [[], [1]] as the output. Can you think why the output is so?

Hint 2

We can see that one subset includes a number, and another does not. From this, we can conclude that we need to find the subsets that include a number and those that do not. This results in 2^n subsets for an array of size n because there are many combinations for including and excluding the array of numbers. Since the elements are unique, duplicate subsets will not be formed if we ensure that we don't pick the element more than once in the current subset. Which algorithm is helpful to generate all subsets, and how would you implement it?

Hint 3

We can use backtracking to generate all possible subsets. We iterate through the given array with an index i and an initially empty temporary list representing the current subset. We recursively process each index, adding the corresponding element to the current subset and continuing, which results in a subset that includes that element. Alternatively, we skip the element by not adding it to the subset and proceed to the next index, forming a subset without including that element. What can be the base condition to end this recursion?

Hint 4

When the index i reaches the end of the array, we append a copy of the subset formed in that particular recursive path to the result list and return. All subsets of the given array are generated from these different recursive paths, which represent various combinations of "include" and "not include" steps for the elements of the array. As we are only iterating from left to right in the array, we don't pick an element more than once.

Company Tags

Amazon11 Wix4 Coupang3 Google3 Infosys3 PayPal3 Tiktok3 Uber3 Agoda2 Bloomberg2 ByteDance2 IBM2 Meta2 Microsoft2 Oracle2 TCS2 Walmart Labs2

Prerequisites

Before attempting this problem, you should be comfortable with:

Recursion - Used to explore the decision tree where each element is either included or excluded
Backtracking - Needed to undo choices (remove elements) after exploring one branch of the decision tree
Bit Manipulation - Alternative approach uses bitmasks to represent subset membership

1. Backtracking

Intuition

The idea is to build all possible subsets by making a choice at each step:
for every number, we have two options — include it or exclude it.
This naturally forms a decision tree.

Backtracking helps us explore both choices:

Add the current number → explore further
Remove it (undo) → explore without it

Whenever we reach the end of the array, the current list represents one
complete subset, so we store it.

This systematically generates all 2ⁿ subsets.

Algorithm

Maintain:
- res → final list of all subsets
- subset → current subset being built
Define a recursive function dfs(i):
- If i equals the length of the input:
  - Add a copy of subset to res
  - Return
- Choice 1: include nums[i]
  - Append number to subset
  - Recurse to next index
  - Remove the number (backtrack)
- Choice 2: skip nums[i]
  - Recurse to next index
Start recursion with dfs(0)
Return res

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []

        def dfs(i):
            if i >= len(nums):
                res.append(subset.copy())
                return
            subset.append(nums[i])
            dfs(i + 1)
            subset.pop()
            dfs(i + 1)

        dfs(0)
        return res

public class Solution {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> subset = new ArrayList<>();
        dfs(nums, 0, subset, res);
        return res;
    }

    private void dfs(int[] nums, int i, List<Integer> subset, List<List<Integer>> res) {
        if (i >= nums.length) {
            res.add(new ArrayList<>(subset));
            return;
        }
        subset.add(nums[i]);
        dfs(nums, i + 1, subset, res);
        subset.remove(subset.size() - 1);
        dfs(nums, i + 1, subset, res);
    }
}

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> subset;
        dfs(nums, 0, subset, res);
        return res;
    }

private:
    void dfs(const vector<int>& nums, int i, vector<int>& subset, vector<vector<int>>& res) {
        if (i >= nums.size()) {
            res.push_back(subset);
            return;
        }
        subset.push_back(nums[i]);
        dfs(nums, i + 1, subset, res);
        subset.pop_back();
        dfs(nums, i + 1, subset, res);
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number[][]}
     */
    subsets(nums) {
        const res = [];
        const subset = [];
        this.dfs(nums, 0, subset, res);
        return res;
    }

    /**
     * @param {number[]} nums
     * @param {number} i
     * @param {number[]} subset
     * @param {number[][]} res
     * @return {void}
     */
    dfs(nums, i, subset, res) {
        if (i >= nums.length) {
            res.push([...subset]);
            return;
        }
        subset.push(nums[i]);
        this.dfs(nums, i + 1, subset, res);
        subset.pop();
        this.dfs(nums, i + 1, subset, res);
    }
}

public class Solution {

    public List<List<int>> Subsets(int[] nums) {
        var res = new List<List<int>>();
        var subset = new List<int>();
        Dfs(nums, 0, subset, res);
        return res;
    }

    private void Dfs(int[] nums, int i, List<int> subset, List<List<int>> res) {
        if (i >= nums.Length) {
            res.Add(new List<int>(subset));
            return;
        }
        subset.Add(nums[i]);
        Dfs(nums, i + 1, subset, res);
        subset.RemoveAt(subset.Count - 1);
        Dfs(nums, i + 1, subset, res);
    }
}

func subsets(nums []int) [][]int {
    res := [][]int{}
    subset := []int{}

    var dfs func(int)
    dfs = func(i int) {
        if i >= len(nums) {
            temp := make([]int, len(subset))
            copy(temp, subset)
            res = append(res, temp)
            return
        }
        subset = append(subset, nums[i])
        dfs(i + 1)
        subset = subset[:len(subset)-1]
        dfs(i + 1)
    }

    dfs(0)
    return res
}

class Solution {
    fun subsets(nums: IntArray): List<List<Int>> {
        val res = mutableListOf<List<Int>>()
        val subset = mutableListOf<Int>()

        fun dfs(i: Int) {
            if (i >= nums.size) {
                res.add(subset.toList())
                return
            }
            subset.add(nums[i])
            dfs(i + 1)
            subset.removeAt(subset.size - 1)
            dfs(i + 1)
        }

        dfs(0)
        return res
    }
}

class Solution {
    func subsets(_ nums: [Int]) -> [[Int]] {
        var res = [[Int]]()
        var subset = [Int]()

        func dfs(_ i: Int) {
            if i >= nums.count {
                res.append(subset)
                return
            }
            subset.append(nums[i])
            dfs(i + 1)
            subset.removeLast()
            dfs(i + 1)
        }

        dfs(0)
        return res
    }
}

impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = Vec::new();
        let mut subset = Vec::new();
        Self::dfs(&nums, 0, &mut subset, &mut res);
        res
    }

    fn dfs(nums: &[i32], i: usize, subset: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
        if i >= nums.len() {
            res.push(subset.clone());
            return;
        }
        subset.push(nums[i]);
        Self::dfs(nums, i + 1, subset, res);
        subset.pop();
        Self::dfs(nums, i + 1, subset, res);
    }
}

Time & Space Complexity

Time complexity: $O(n * 2 ^ n)$
Space complexity:
- $O(n)$ extra space.
- $O(2 ^ n)$ for the output list.

2. Iteration

Intuition

Start with just one subset: the empty set [].

For every number in the array, we take all the subsets we have so far and
create new subsets by adding the current number to each of them.

Example:

Start: [[]]
Add 1 → [[], [1]]
Add 2 → [[], [1], [2], [1,2]]
Add 3 → [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Each step doubles the number of subsets.

Algorithm

Initialize res = [[]] (start with empty subset).
For each number num in the input array:
- For every subset already in res:
  - Create a new subset that includes num
- Append all these newly created subsets to res.
Return res after processing all numbers.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]

        for num in nums:
            res += [subset + [num] for subset in res]

        return res

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());

        for (int num : nums) {
            int size = res.size();
            for (int i = 0; i < size; i++) {
                List<Integer> subset = new ArrayList<>(res.get(i));
                subset.add(num);
                res.add(subset);
            }
        }

        return res;
    }
}

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res = {{}};

        for (int num : nums) {
            int size = res.size();
            for (int i = 0; i < size; i++) {
                vector<int> subset = res[i];
                subset.push_back(num);
                res.push_back(subset);
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number[][]}
     */
    subsets(nums) {
        let res = [[]];

        for (let num of nums) {
            let size = res.length;
            for (let i = 0; i < size; i++) {
                let subset = res[i].slice();
                subset.push(num);
                res.push(subset);
            }
        }

        return res;
    }
}

public class Solution {
    public List<List<int>> Subsets(int[] nums) {
        List<List<int>> res = new List<List<int>>();
        res.Add(new List<int>());

        foreach (int num in nums) {
            int size = res.Count;
            for (int i = 0; i < size; i++) {
                List<int> subset = new List<int>(res[i]);
                subset.Add(num);
                res.Add(subset);
            }
        }

        return res;
    }
}

class Solution {
    fun subsets(nums: IntArray): List<List<Int>> {
        val res = mutableListOf<List<Int>>(listOf())

        for (num in nums) {
            val n = res.size
            for (i in 0 until n) {
                val newSubset = res[i].toMutableList()
                newSubset.add(num)
                res.add(newSubset)
            }
        }

        return res
    }
}

class Solution {
    func subsets(_ nums: [Int]) -> [[Int]] {
        var res: [[Int]] = [[]]

        for num in nums {
            res += res.map { $0 + [num] }
        }

        return res
    }
}

impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res: Vec<Vec<i32>> = vec![vec![]];

        for &num in &nums {
            let size = res.len();
            for i in 0..size {
                let mut subset = res[i].clone();
                subset.push(num);
                res.push(subset);
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n * 2 ^ n)$
Space complexity:
- $O(n)$ extra space.
- $O(2 ^ n)$ for the output list.

3. Bit Manipulation

Intuition

Every subset can be represented using bits.

For an array of length n, there are 2^n possible subsets.
Each subset corresponds to a number from 0 to 2^n - 1.

Example for nums = [a, b, c]:

000 → choose nothing → []
001 → choose c
010 → choose b
011 → choose b, c
100 → choose a
...and so on.

Each bit tells us whether to include the corresponding element.

So for every integer i from 0 to (1 << n) - 1:

Check each bit j of i
If bit j is 1, include nums[j] in the current subset.

Algorithm

Let n be the length of nums.
Loop i from 0 to (1 << n) - 1 (this generates all bitmasks).
For each i, build a subset:
- For each position j from 0 to n - 1:
  - If the j-th bit of i is set, include nums[j] in the subset.
Add the subset to the result list.
Return all subsets.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        for i in range(1 << n):
            subset = [nums[j] for j in range(n) if (i & (1 << j))]
            res.append(subset)
        return res

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
            List<Integer> subset = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    subset.add(nums[j]);
                }
            }
            res.add(subset);
        }
        return res;
    }
}

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        for (int i = 0; i < (1 << n); i++) {
            vector<int> subset;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    subset.push_back(nums[j]);
                }
            }
            res.push_back(subset);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number[][]}
     */
    subsets(nums) {
        let res = [];
        let n = nums.length;
        for (let i = 0; i < 1 << n; i++) {
            let subset = [];
            for (let j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    subset.push(nums[j]);
                }
            }
            res.push(subset);
        }
        return res;
    }
}

class Solution {
    fun subsets(nums: IntArray): List<List<Int>> {
        val n = nums.size
        val res = mutableListOf<List<Int>>()

        for (i in 0 until (1 shl n)) {
            val subset = mutableListOf<Int>()
            for (j in 0 until n) {
                if (i and (1 shl j) != 0) {
                    subset.add(nums[j])
                }
            }
            res.add(subset)
        }

        return res
    }
}

class Solution {
    func subsets(_ nums: [Int]) -> [[Int]] {
        let n = nums.count
        var res: [[Int]] = []

        for i in 0..<(1 << n) {
            var subset: [Int] = []
            for j in 0..<n {
                if (i & (1 << j)) != 0 {
                    subset.append(nums[j])
                }
            }
            res.append(subset)
        }

        return res
    }
}

impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let n = nums.len();
        let mut res = Vec::new();

        for i in 0..(1 << n) {
            let mut subset = Vec::new();
            for j in 0..n {
                if i & (1 << j) != 0 {
                    subset.push(nums[j]);
                }
            }
            res.push(subset);
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n * 2 ^ n)$
Space complexity:
- $O(n)$ extra space.
- $O(2 ^ n)$ for the output list.

Common Pitfalls

Modifying the Subset After Adding to Result

When adding a subset to the result list, you must add a copy of the current subset. Otherwise, backtracking modifications will alter subsets already in the result.

# Wrong: adds reference that gets modified later
res.append(subset)
# Correct: add a copy
res.append(subset[:])  # or list(subset)

Forgetting the Empty Subset

The power set always includes the empty subset []. Forgetting to initialize with an empty subset or starting the iteration incorrectly will miss this case.

Incorrect Index Handling in Backtracking

When recursing, start from i + 1 to avoid reusing the same element and to prevent duplicate subsets. Starting from 0 or i generates incorrect results.

# Wrong: includes current element again
for j in range(i, len(nums)):
# Correct: start from next element
for j in range(i + 1, len(nums)):

Integer Overflow in Bitmask Approach

For the bitmask solution, 1 << n can overflow for large n. In most languages, this limits the approach to around 30 elements, though problem constraints usually keep n small.