Subsets（子集）

题目 / Problem

中文： 给定一个由互不相同的整数组成的数组 nums，返回所有可能的子集，也就是该数组的幂集。

结果中不能包含重复子集，可以按任意顺序返回。

English: Given an integer array nums containing unique elements, return all possible subsets—the power set.

The solution must not contain duplicate subsets and may be returned in any order.

示例 / Examples

Example 1

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

结果顺序不重要，下面的顺序同样正确：
The output order does not matter, so the following order is also valid:

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

Example 2

Input:  nums = [0]
Output: [[],[0]]

空集也是任何集合的子集，因此结果始终包含 []。
The empty set is a subset of every set, so the result always contains [].

约束 / Constraints

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中所有数字互不相同。
  All numbers in nums are unique.

解题思路：回溯 / Approach: Backtracking

使用 path 表示当前构造出的子集。与全排列不同，子集不要求长度必须达到 nums.length；搜索树中的每个节点都代表一个合法子集。
Use path to represent the subset currently being built. Unlike permutations, a subset does not need to reach length nums.length; every node in the search tree represents a valid subset.

因此，每次进入递归函数时，都先把当前 path 的副本加入结果：
Therefore, whenever the recursive function is entered, first add a copy of path to the result:

result.push([...path]);

随后，从 start 开始选择后续元素：
Then choose subsequent elements starting from start:

1. 把 nums[i] 加入当前子集。
   Add nums[i] to the current subset.
2. 从 i + 1 开始递归，保证每个元素最多使用一次。
   Recurse from i + 1, ensuring each element is used at most once.
3. 递归返回后移除 nums[i]，尝试下一个选择。
   Remove nums[i] after recursion and try the next choice.

为什么使用 start？ / Why Use start?

子集只关心包含哪些元素，不关心元素的选择顺序。例如 [1,2] 和 [2,1] 表示同一个子集。
Subsets care only about which elements are included, not the order in which they are chosen. For example, [1,2] and [2,1] represent the same subset.

递归时只允许选择当前下标之后的元素，可以保证每个组合只生成一次：
Allowing only elements after the current index ensures that every combination is generated exactly once:

选择 nums[i] 后，下一层从 i + 1 开始
After choosing nums[i], the next level starts at i + 1

这样会生成 [1,2]，但不会再生成 [2,1]。
This generates [1,2] but never generates [2,1].

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function subsets(nums) {
  const result = [];
  const path = [];

  function backtrack(start) {
    // 搜索树中的每个节点都是一个合法子集
    // Every node in the search tree is a valid subset
    result.push([...path]);

    for (let i = start; i < nums.length; i++) {
      // 做出选择 / Make a choice
      path.push(nums[i]);

      // 每个元素最多选择一次 / Use each element at most once
      backtrack(i + 1);

      // 撤销选择 / Undo the choice
      path.pop();
    }
  }

  backtrack(0);
  return result;
}

执行过程 / Walkthrough

以 nums = [1,2,3] 为例，回溯搜索树为：
For nums = [1,2,3], the backtracking search tree is:

[]
├── [1]
│   ├── [1,2]
│   │   └── [1,2,3]
│   └── [1,3]
├── [2]
│   └── [2,3]
└── [3]

每个节点都会加入结果，因此得到：
Every node is added to the result, producing:

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

选择与撤销 / Choose and Undo

例如完成 [1,2,3] 后，回溯过程如下：
For example, after completing [1,2,3], backtracking proceeds as follows:

[1,2,3] → 移除 3 → [1,2]
[1,2]   → 移除 2 → [1]
[1]     → 选择 3 → [1,3]

path.pop() 让同一个数组可以被不同递归分支复用。
path.pop() allows the same array to be reused across different recursive branches.

为什么共有 2^n 个子集？ / Why Are There 2^n Subsets?

对于每个元素，都有两种独立选择：
Each element has two independent choices:

选择它 / Include it
不选择它 / Exclude it

n 个元素一共有：
For n elements, this gives:

2 × 2 × ... × 2 = 2^n

因此任何生成全部子集的算法都至少需要处理 2^n 个结果。
Therefore, any algorithm that generates the full power set must process at least 2^n results.

另一种方法：迭代扩展 / Alternative: Iterative Expansion

也可以从空集开始，每遇到一个数字，就复制所有已有子集并加入这个数字：
Starting from the empty set, another approach copies every existing subset and appends the current number:

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

  for (const num of nums) {
    const currentSize = result.length;

    for (let i = 0; i < currentSize; i++) {
      result.push([...result[i], num]);
    }
  }

  return result;
}

对于 [1,2,3]：
For [1,2,3]:

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

两种方法的渐进复杂度相同。回溯法更容易扩展到需要额外约束的组合问题。
Both methods have the same asymptotic complexity. Backtracking is easier to extend to combination problems with additional constraints.

复杂度 / Complexity

设 n = nums.length。共有 2^n 个子集，每个子集最多需要复制 n 个元素。
Let n = nums.length. There are 2^n subsets, and copying one subset may take up to O(n) time.

• 时间复杂度 / Time: O(n × 2^n)
• 辅助空间 / Auxiliary space: O(n)，用于递归栈和当前路径，不包括返回结果。
  O(n) for the recursion stack and current path, excluding the result.
• 结果空间 / Output space: O(n × 2^n)

易错点 / Common Pitfalls

• 空集 [] 也是合法子集，必须包含在结果中。
  The empty set [] is valid and must be included.
• 每次进入递归函数都要记录当前 path，而不是只在到达固定长度时记录。
  Record path at every recursive call, not only at a fixed length.
• 保存结果时必须复制 path，不能直接保存同一个数组引用。
  Copy path when saving it instead of storing the same array reference.
• 下一层递归要从 i + 1 开始，防止重复选择同一个元素或生成顺序不同的重复子集。
  Recurse from i + 1 to avoid reusing an element or generating reordered duplicates.
• 本题元素互不相同，因此不需要排序和跳过重复值；如果输入可能重复，则需要额外去重。
  Values are unique here, so sorting and duplicate skipping are unnecessary. Extra handling would be needed if duplicates were allowed.