78. Subsets Medium

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

Approach

Input: Given an integer array nums without duplicate elements.

Output: Return all possible subsets of the array.

This problem is a typical Subset Backtracking problem. The core idea is to use a backtracking algorithm to explore the "select" and "do not select" cases for all elements.

Three Questions of Backtracking

1. Current Operation?

   • At the current position i, try selecting the current number nums[j] (j ∈ [i, n)) and add it to the current subset path.
   • Namely, placing nums[j] into the path, representing "I selected this number".

2. Sub-problem?

   • After choosing nums[j], we need to continue recursively processing the remaining numbers.
   • That is, proceeding from position j+1, continue picking numbers onwards, ensuring no duplicate selection (each number is selected at most once).

3. Next Sub-problem?

   • The next recursion step is dfs(j+1), indicating proceeding from the next position to continue selecting numbers until the whole array is traversed.

Pruning Conditions

• This problem itself doesn't have an explicit pruning condition. You can choose or not choose the current number every time. Using the left-to-right recursion approach prevents generating duplicate subsets (guaranteeing order).

Implementation

Method 1: Choose/Don't Choose (Recursive Binary Tree)

For each element, there are two possibilities: "choose" and "don't choose", just like the left and right branches of a binary tree.

1. Do Not Choose Current Element Directly enter dfs(i + 1), recursing to the next element.
2. Choose Current Element
   • Add the current element to path.
   • Continue into dfs(i + 1), recursing to the next element.
   • Upon backtracking (undoing the choice), perform path.pop() to remove the current element, preventing it from affecting other branches.
3. Recursion Exit Condition When index i exceeds the array length, copy the current path into ans, completing the preservation of one full subset.

The characteristic of this method is: Results are collected only at the leaf nodes (when traversed to the end of the array).

python

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []  # Used to store all subsets
        path = []  # The subset currently being constructed
        n = len(nums)  # The length of the array

        def dfs(i):
            """
            Depth-First Search, generate subsets
            i: index of the element currently considered
            """
            # If all numbers are considered, add the current subset path to the answer
            if i >= n:
                ans.append(path.copy())  # Must use copy() to avoid reference issues
                return

            # Option 1: Do not choose the current element, skip to the next element directly
            dfs(i + 1)

            # Option 2: Choose the current element
            path.append(nums[i])
            dfs(i + 1)  # Recurse to the next element

            # Backtrack, undo the choice
            path.pop()

        # Start recursion from 0-th element
        dfs(0)
        return ans

javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const subsets = function(nums) {
    const ans = [];
    const path = [];
    
    function dfs(i) {
        if (i >= nums.length) {
            ans.push([...path]);
            return;
        }

        dfs(i + 1);

        path.push(nums[i]);
        dfs(i + 1);
        path.pop();
    }

    dfs(0);
    return ans;
};

Method 2: Collect Results at Every Traversal Step

We can add the current path to the result at every layer of recursion, because subsequent elements can all be skipped.

1. Record Result at Every Recursion Because every path corresponds to a subset, entering the recursion means adding the current path into ans.
2. Traverse All Branches Use a loop from the current index i to the end of the array, trying to select each element.
   • Select current element nums[j], append to path.
   • Recurse into the next layer dfs(j + 1).
   • Perform path.pop() when backtracking (undoing the choice).
3. Recursion Exit Condition When the index exceeds array length, the function naturally returns.

The characteristic of this method is: Results are collected at every recursion level, and duplication is prevented by the for loop.

python

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []  # Used to store all subsets
        path = []  # Current subset being constructed
        n = len(nums)  # Array length

        def dfs(index: int):
            """
            index: index of the element currently considered
            """
            # Add the current path to the answer directly, as every step can be a valid subset
            ans.append(path.copy())

            # Starting from the current index, try adding subsequent elements sequentially
            for i in range(index, n):
                # Choose current element
                path.append(nums[i])
                # Recursively enter the next layer
                dfs(i + 1)
                # Undo choice, backtrack
                path.pop()

        dfs(0)
        return ans

javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const subsets = function(nums) {
    const ans = [];
    const path = [];
    
    function dfs(i) {
        ans.push([...path]);
        if (i >= nums.length) return;

        for (let j = i; j < nums.length; j++) {
            path.push(nums[j]);
            dfs(j + 1);
            path.pop();
        }
    }

    dfs(0);
    return ans;
};

Complexity Analysis

• Time Complexity: O(n * 2^n)
• Space Complexity: O(n * 2^n)

Links

78. Subsets (English)

78. 子集 (Chinese)