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

【算法】子集

news 2025/6/28 17:35:45

难度：中等

题目：

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

解题思路：

解决这道题目的关键在于理解并应用回溯算法来生成所有可能的子集。回溯算法是一种通过试错来寻找解的方法，当发现现有的路径不符合解的条件时，会回退到上一步，尝试其他可能的路径。对于子集问题，我们可以通过递归的方式，逐个决定每个元素是否加入当前子集中。

定义递归函数：设一个递归函数，接收当前子集、当前遍历到的数组下标作为参数。
递归终止条件：当遍历到数组末尾时，将当前子集添加到结果集中，然后返回。
单层递归逻辑：

将当前元素加入子集，然后递归调用下一个元素。
回溯：从子集中移除当前元素（即不选择当前元素），然后递归调用下一个元素。
这样，每个元素都有“选”或“不选”两种选择，从而生成所有可能的子集。

JavaScript 实现：

function subsets(nums) {const result = []; // 存储所有子集的数组const backtrack = (start, path) => {// 将当前子集添加到结果集中result.push([...path]);// 遍历数组，从start开始，避免重复选择for (let i = start; i < nums.length; i++) {// 选择当前元素，加入路径path.push(nums[i]);// 递归调用，进入下一层决策树backtrack(i + 1, path);// 回溯，撤销选择，回到上一层决策树path.pop();}};// 调用回溯函数，初始时子集为空，从数组第一个元素开始考虑backtrack(0, []);return result;
}// 示例
const nums = [1, 2, 3];
console.log(subsets(nums)); // 应输出所有子集