Subsets

Concept

LeetCode #78.
Problem: Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

If the input is [1, 2, 3], a subset does not need to use all 3 numbers.
Valid subsets: [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3].

The mathematical size of a power set is exactly $2^N$.
Why? Because for every single number in the array, you make exactly 2 choices: “Do I include this number, or do I exclude it?”

The Strategy

Because we are picking numbers in order, we do not need a used Set like we did in Permutations. We just pass a startIndex parameter down the recursion.

In Permutations, we only saved the result when the array was full.
In Subsets, every single node in the recursive tree is a valid answer! We literally just push a clone of the currentPath into the results array at the very top of the function, before doing any math.

Implementation

// Time Complexity: O(N * 2^N) (2^N subsets, takes O(N) to clone each into the result)
// Space Complexity: O(N) (Call stack depth)

function subsets(nums: number[]): number[][] {
    const result: number[][] = [];
    const currentPath: number[] = [];

    function backtrack(startIndex: number) {
        // 1. BASE CASE / SAVING:
        // Every single step we take forms a valid subset! Save it immediately.
        result.push([...currentPath]);

        // 2. EXPLORE: Start looping from the current index to the end
        // (This naturally prevents us from walking backwards and creating 
        // duplicate combinations like [2, 1] when we already have [1, 2])
        for (let i = startIndex; i < nums.length; i++) {
            // 3. DO: Include the current number
            currentPath.push(nums[i]);

            // 4. RECURSE: Move to the NEXT index
            backtrack(i + 1);

            // 5. UNDO: Exclude the number so we can try the next branch
            currentPath.pop();
        }
    }

    backtrack(0);
    return result;
}

The “Include/Exclude” Approach (Alternative)

Instead of using a for loop, you can explicitly code the $2^N$ math. At every index, you literally write two recursive calls: one that includes the number, and one that doesn’t.
This approach is sometimes easier for beginners to visualize as a strict Binary Tree of decisions.

function subsetsIncludeExclude(nums: number[]): number[][] {
    const result: number[][] = [];
    const currentPath: number[] = [];

    function dfs(index: number) {
        // Base Case: We made a choice for every single number.
        if (index === nums.length) {
            result.push([...currentPath]);
            return;
        }

        // Choice 1: INCLUDE the number at the current index
        currentPath.push(nums[index]);
        dfs(index + 1);
        
        // Choice 2: EXCLUDE the number at the current index
        currentPath.pop(); // Undo the inclusion
        dfs(index + 1);
    }

    dfs(0);
    return result;
}

Interview Questions

Q: What happens if the input array has duplicate numbers, like [1, 2, 2]?
A: This is LeetCode #90 (Subsets II). Just like Permutations II, standard backtracking will generate identical duplicate subsets (like two different [1, 2] arrays).
You solve it exactly the same way:

1. Sort the input array first ([1, 2, 2]).
2. Inside the for loop, add if (i > startIndex && nums[i] === nums[i - 1]) continue;.
   This mathematically skips the duplicate branch only if we are choosing a sibling on the same horizontal level of the tree, perfectly pruning the duplicate subset while still allowing vertical inclusion (so [1, 2, 2] is legally formed).