Subsets (Power Set) - Complete Backtracking Guide

Introduction

The Subsets problem, often referred to as generating the Power Set, is a fundamental problem in computer science and algorithm design. It serves as an excellent gateway to understanding Backtracking.

Given a set of distinct integers, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

What is a Power Set?

The power set of a set $S$ is the set of all subsets of $S$, including the empty set and $S$ itself. If a set has $N$ elements, its power set has $2^N$ elements.

For example, if $S = [1, 2, 3]$, the power set is:

[ [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] ]

The Backtracking Approach

Backtracking is a systematic way to iterate through all possible configurations of a problem. It is essentially a depth-first search (DFS) with pruning.

Core Logic: Include or Exclude

For every element in the array, we have exactly two choices:

1. Include the element in the current subset.
2. Exclude the element from the current subset.

By making these binary decisions for every element, we naturally generate all possible combinations.

Algorithm Steps

1. Initialization: Create an empty array path to store the current subset being built and an array result to store all valid subsets.
2. Recursive Function: Define a function backtrack(startIndex).

• Base Case: If startIndex reaches the length of the input array, we have explored all elements. Push a copy of path into result.
• Recursive Step: Iterate i from startIndex to the end of the array.
• Action: Add nums[i] to path.
• Recurse: Call backtrack(i + 1) to explore further elements.
• Backtrack: Remove nums[i] from path (this is the crucial step). This resets the state for the next iteration of the loop.

1. Start: Call backtrack(0) to begin the process.

Visualizing the Recursion Tree

Imagine the array [1, 2, 3]:

Start (Index 0)
├── Include 1
│   ├── Include 2
│   │   ├── Include 3 -> Push [1,2,3]
│   │   └── Exclude 3 -> Push [1,2]
│   └── Exclude 2
│       ├── Include 3 -> Push [1,3]
│       └── Exclude 3 -> Push [1]
└── Exclude 1
    ├── Include 2
    │   ├── Include 3 -> Push [2,3]
    │   └── Exclude 3 -> Push [2]
    └── Exclude 2
        ├── Include 3 -> Push [3]
        └── Exclude 3 -> Push []

Code Implementation

TypeScript/JavaScript

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

  function backtrack(startIndex: number) {
    // Add a copy of the current path to the result
    result.push([...path]);

    // Iterate through the remaining elements
    for (let i = startIndex; i < nums.length; i++) {
      // Action: Include nums[i]
      path.push(nums[i]);

      // Recurse: Move to the next index
      backtrack(i + 1);

      // Backtrack: Remove nums[i] to explore the 'exclude' branch
      path.pop();
    }
  }

  backtrack(0);
  return result;
}

Python

def subsets(nums):
    result = []
    path = []

    def backtrack(start):
        result.append(path.copy())
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Complexity Analysis

Time Complexity: $O(N imes 2^N)$

• Number of Subsets: There are $2^N$ subsets in the power set.
• Copying: For each subset, we create a new array (using [...path] or .copy()) which takes $O(N)$ time.
• Total: $2^N imes N$.

Space Complexity: $O(N)$

• Auxiliary Space: The recursion stack goes as deep as $N$ (when we include every element).
• Output Space: The space required to store the result is $O(N imes 2^N)$, which is unavoidable as we must store all subsets.

Handling Duplicates

If the input array contains duplicates (e.g., [1, 2, 2]), the naive approach will generate duplicate subsets like [1, 2] and [1, 2].

Solution Strategy

1. Sort the input array first.
2. In the loop, if i > startIndex and nums[i] == nums[i-1], skip the current iteration.

function subsetsWithDup(nums: number[]): number[][] {
  const result: number[][] = [];
  const path: number[] = [];

  // Sort to handle duplicates easily
  nums.sort((a, b) => a - b);

  function backtrack(startIndex: number) {
    result.push([...path]);

    for (let i = startIndex; i < nums.length; i++) {
      // Skip duplicates: if current element is same as previous and not the first in this level
      if (i > startIndex && nums[i] === nums[i - 1]) {
        continue;
      }

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

  backtrack(0);
  return result;
}

Common Mistakes

1. Not Copying the Path: If you push path directly into result, all entries in result will point to the same reference. You must push a copy of the array ([...path] or path.slice()).
2. Incorrect Backtracking: Forgetting to pop() the element after the recursive call causes the path to grow indefinitely and leads to incorrect results.
3. Index Management: Using i instead of i + 1 in the recursive call will cause infinite recursion or incorrect subsets because it allows reusing the same element multiple times in one subset.

Real-World Applications

• Database Queries: Generating all possible combinations of filter criteria.
• Feature Flags: Evaluating all possible combinations of enabled/disabled features.
• Cryptography: Generating keys and permutations.
• Game Development: Exploring all possible moves or board states in a game tree.

Summary

The Subsets problem is the quintessential backtracking problem. It teaches the pattern of building a solution incrementally and undoing changes (backtracking) when a path doesn't lead to a valid solution. Mastering this pattern is essential for solving problems like Permutations, Combination Sum, and Subsets II.