数组子集

题目#

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1

输入：nums = [1,2,3] 输出：[ [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3] ]

示例 2

输入：nums = [0] 输出：[ [], [0] ]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

解题思路#

这道题其实和我们前面所做的组合的题目也是非常相似的。这里以 nums = [1,2,3] 为例画出抽象树结构：

对于给定数组 nums（其中元素互不相同），我们要求所有可能的子集，也就是每个元素都有“选”与“不选”的两种可能。回溯算法非常适合这种枚举问题，基本思路如下：

1. 回溯框架：定义一个辅助函数 backtrack(start)，其中：
   • start 表示当前处理到数组的下标。
   • 同时维护一个临时数组 path，表示当前已经选中的元素（即当前形成的子集）。
2. 收集结果：在递归过程中，每经过一个状态，就将当前的 path（复制后）加入到结果数组中，因为每个状态都是一个合法的子集（包括空集）。
3. 递归过程：对于当前 start 到数组末尾的每个下标 i：
   • 选择 nums[i]，将其加入 path。
   • 然后递归调用 backtrack(i+1)，这样确保不会重复选择之前的元素，也保证子集中的顺序。
   • 递归返回后，通过 path.pop() 撤销选择（回溯），以便尝试其他组合。
4. 终止条件：当 start 达到数组长度时，表示已经处理完所有元素，此时返回上一层。实际上，由于我们在每个状态都将当前的 path 添加到结果中，所以不需要单独的终止条件。

这样，我们就能遍历所有从 nums 中选取元素的组合，得到完整的子集集合。

🙋提问：这个题目需要剪枝么？

这道题目其实也是不需要剪枝的，因为要求返回所有的子集，每一个组合都是有效的组合。不存在“无效分支”。

代码实现

/**
 * nums - 是一个数组，例如 [1,2]
 * returns - 所有子集的数组
 */
function subsets(nums) {
  const results = [] // 存放最终的结果
  const path = [] // 临时数组，表示当前选中的子集

  /**
   * start - 数组中每个数的下标
   */
  function backtrack(start) {
    results.push([...path])

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i])
      backtrack(i + 1)
      path.pop()
    }
  }
  backtrack(0)

  return results
}

-EOF-