怎么在自己的电脑上做网站,网页美工设计软件,全球搜索,linux服务器下如何新建网站难度#xff1a;中等
题目#xff1a;
给你一个整数数组 nums #xff0c;数组中的元素 互不相同 。返回该数组所有可能的 子集#xff08;幂集#xff09;。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1#xff1a;
输入#xff1a;nums [1,…难度中等
题目
给你一个整数数组 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)); // 应输出所有子集这段代码首先定义了一个subsets函数它接收一个整数数组nums作为参数。在这个函数内部定义了backtrack递归函数用于生成所有子集。通过不断地选择和不选择当前元素递归遍历整个决策树最终将所有符合条件的子集收集到result数组中。最后返回这个包含所有子集的数组。
