当前位置：首页 > news >正文

一起学习LeetCode热题100道（56/100）

news 2025/8/23 0:47:49

56.子集(学习)

给你一个整数数组 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 中的所有元素互不相同

解析:
一、初始化：
1.创建一个空数组 result 来存储所有生成的子集。
2.定义一个名为 backtrack 的函数，它接受两个参数：startIndex（当前考虑的起始索引）和 currentSubset（当前正在构建的子集）。

二、回溯函数：
1.基准情况：当回溯函数被调用时，首先将当前子集（可能为空）添加到结果集 result 中。这是因为每个位置都可以选择不添加任何元素，从而形成一个更短的子集。
2.递归遍历：
2.1.使用一个循环从 startIndex 遍历到 nums.length。在每一步中，我们考虑将 nums[i] 添加到当前子集中。
2.2.在将元素添加到 currentSubset 之后，我们递归地调用 backtrack 函数，但这次传递的 startIndex 是 i + 1。这样做是为了确保在下一层递归中，我们不会重复选择已经添加过的元素（即，我们不会考虑 nums[i] 之后的元素作为当前子集的第一个元素）。
2.3.在递归调用返回后，我们需要将刚刚添加到 currentSubset 中的元素移除（回溯），以便在下一次循环迭代中尝试不同的元素组合。

三、启动回溯：
1.从索引 0 开始调用 backtrack 函数，并传入一个空数组作为初始的 currentSubset。这表示我们从空集开始构建子集。

四、返回结果：
1.当所有可能的子集都被生成并添加到 result 后，我们返回 result。

var subsets = function (nums) {const result = [];// 定义回溯函数  const backtrack = (startIndex, currentSubset) => {// 将当前子集添加到结果集中  result.push([...currentSubset]);for (let i = startIndex; i < nums.length; i++) {// 将当前元素添加到当前子集中  currentSubset.push(nums[i]);// 递归调用，注意起始索引增加，避免重复选择  backtrack(i + 1, currentSubset);// 回溯，撤销选择  currentSubset.pop();}};// 从空集开始回溯  backtrack(0, []);return result;
};