Problem Description

Given an integer array nums with distinct elements, return all possible subsets (the power set).

The solution set cannot contain duplicate subsets. You may return the subsets in any order.

Example:

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

Algorithm Analysis

The backtracking approach treats subset generation as a binary decision tree. At each index position, we make one of two choices:

• Include the current element in the subset
• Exclude the current element from the subset

This creates a systematic exploration of all possible combinations, where each node in the recursion tree represents a valid subset.

Implementation

#include <iostream>
#include <vector>

class SubsetGenerator {
private:
    std::vector<int> current;
    std::vector<std::vector<int>> result;
    
    void explore(int position, const std::vector<int>& input) {
        if (position == input.size()) {
            result.push_back(current);
            return;
        }
        
        // Decision 1: Include current element
        current.push_back(input[position]);
        explore(position + 1, input);
        current.pop_back();
        
        // Decision 2: Exclude current element
        explore(position + 1, input);
    }
    
public:
    std::vector<std::vector<int>> generate(std::vector<int>& input) {
        explore(0, input);
        return result;
    }
};

Alternative Implementation

class PowerSetBuilder {
private:
    std::vector<std::vector<int>> collection;
    
    void backtrack(int index, const std::vector<int>& source, 
                   std::vector<int>& target) {
        collection.push_back(target);
        
        for (int i = index; i < source.size(); ++i) {
            target.push_back(source[i]);
            backtrack(i + 1, source, target);
            target.pop_back();
        }
    }
    
public:
    std::vector<std::vector<int>> build(std::vector<int>& input) {
        std::vector<int> temp;
        backtrack(0, input, temp);
        return collection;
    }
};

Complexity Analysis

The algorithm generates 2^n subsets for an array of length n, where n is the size of the input array.

• Time Complexity: O(n × 2^n) - Each of the 2^n subsets requires O(n) time to copy into the result
• Space Complexity: O(n) - Recursion depth, excluding the space needed for storing results

Key Insight

The backtracking pattern follows a consistent structure:

1. Record the current state at each recursion level
2. Iterate through available choices from the current position
3. Make a choice and recurse deeper
4. Undo the choice (backtrack) to探索 other branches

This ensures all possible combinations are explored systematically without missing any valid subsets.