04、子集

排列关心顺序，子集只关心选了哪些元素。对于 [1,2,3]，[1,3] 是一个子集，而 [3,1] 不应该被算作另一个答案。

问题与目标

LeetCode 78：子集给定互不相同的整数，返回所有子集，包括空集和原集合。

输入：[1,2]
输出：[[], [1], [1,2], [2]]

返回顺序不影响正确性。n 个不同元素各有选与不选两种状态，因此一共有 2ⁿ 个子集。

起始下标怎样避免重复

让每条路径中的下标严格递增：选了 nums[i]，后面只能从 i + 1 开始选。这样 [1,2] 产生后，不会再走出 [2,1]。

与“必须选满 n 个位置”的全排列不同，子集的每个合法路径都是答案：空路径要收集，选一个元素的路径也要收集，不能只在叶子节点保存结果。

以两个元素走一遍

初始路径 [] 先保存。选择 1 后保存 [1]，继续选 2 保存 [1,2]；撤销这次选择，再撤销 1，回到空路径。空路径再选择 2，保存 [2]。此时 2 后面没有候选，搜索结束。

注意，撤销是为了复原当前路径，不是从结果中删除已保存的子集。push_back(path) 保存的是一份副本。

回溯实现：在每个节点收集

#include <vector>

class Solution {
 public:
  std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
    std::vector<std::vector<int>> answers;
    std::vector<int> path;
    search(nums, 0, path, answers);
    return answers;
  }

 private:
  void search(const std::vector<int>& nums, std::size_t start,
              std::vector<int>& path, std::vector<std::vector<int>>& answers) {
    answers.push_back(path);
    for (std::size_t i = start; i < nums.size(); ++i) {
      path.push_back(nums[i]);
      search(nums, i + 1, path, answers);
      path.pop_back();
    }
  }
};

迭代实现：已有子集各复制一份

从 [[]] 开始。每遇到一个新元素，就给此前的每个子集追加该元素，形成一批新子集。必须先记录旧长度，不能一边追加一边遍历扩大的结果。

#include <vector>

std::vector<std::vector<int>> subsetsIterative(const std::vector<int>& nums) {
  std::vector<std::vector<int>> answers(1);
  for (int value : nums) {
    const std::size_t previous_size = answers.size();
    for (std::size_t i = 0; i < previous_size; ++i) {
      auto next = answers[i];
      next.push_back(value);
      answers.push_back(next);
    }
  }
  return answers;
}

复杂度与边界

两种实现都需要保存 2ⁿ 个子集，复制所有元素的总量是 O(n·2ⁿ)，时间与结果空间均为这个量级。回溯除结果外的路径和栈占 O(n)；迭代版的临时副本最多占 O(n)。

空数组的答案是 [[]]，不是 []。输入有重复数字时，这两版代码不负责去重；那是“子集 II”的问题，需要额外排序与同层剪枝。

常见误区

子集不是组合的固定长度版本，也不是排列。判断应当收集所有路径、固定长度路径还是完整排列，是开始写回溯之前必须想清楚的第一步。