【算法LeetCode】78.子集（回溯）

给你一个整数数组 nums &＃xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集&＃xff08;幂集&＃xff09;。

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

示例 1&＃xff1a;
输入&＃xff1a;nums &＃61; [1,2,3]
输出&＃xff1a;[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2&＃xff1a;
输入&＃xff1a;nums &＃61; [0]
输出&＃xff1a;[[],[0]]

来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
链接&＃xff1a;https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权&＃xff0c;非商业转载请注明出处。

提示&＃xff1a;
1 <&＃61; nums.length <&＃61; 10
-10 <&＃61; nums[i] <&＃61; 10
nums 中的所有元素 互不相同

我的题解

成功前的尝试

一开始我把这道题的暴力解法想得很简单&＃xff0c;就是用两层嵌套的 for 循环&＃xff08;或者理解为两个指针&＃xff09;不断获取 nums 中的某个区间&＃xff0c;把所有区间都存入 result 即可。

/*** &＃64;param {number[]} nums* &＃64;return {number[][]}*/
var subsets &＃61; function(nums) {let result &＃61; [];result.push([]);for(let i &＃61; 0; i < nums.length; i&＃43;&＃43;){for(let j &＃61; 0; j <&＃61; i; j&＃43;&＃43;){result.push(nums.slice(j, i&＃43;1));}}return result;
};


然而这种做法是错误的&＃xff1a;

错误的原因也很明显&＃xff1a;没有考虑到子集中的元素不一定是 nums 中的连续的元素。

我的题解&＃xff08;回溯&＃xff09;

后来我想到了之前利用回溯解决的全排列的题目&＃xff1a;

参考&＃xff1a;【算法-LeetCode】46. 全排列&＃xff08;回溯算法初体验&＃xff09;_赖念安的博客-CSDN博客
参考&＃xff1a;【算法-LeetCode】22. 括号生成&＃xff08;回溯&＃xff1b;有重复元素的全排列&＃xff09;_赖念安的博客-CSDN博客

上面的【LeetCode22】就是在【LeetCode46】的基础上做了一下点改变。于是我就想本题似乎也可以用那种思想来完成。

【LeetCode46.全排列】中的递归结束条件是当 temp 的长度增长到与 nums 一样长的时候结束递归&＃xff0c;且此时 temp 中存储的就是我们想要的一个结果&＃xff0c;所以在结束递归的同时才能将 temp 中的结果存入 result 中。

但是本题的子集只需要所选取的元素是来自于 nums 就可以&＃xff0c;不用考虑长度&＃xff0c;所以不必等 temp 的长度增长到与 nums 一样长时再将 temp 中存储的元素存入 result。

也就是说&＃xff0c;无论 temp 的长度是多少&＃xff0c;它里面存的都是一个符合题目要求的子集结果。但是&＃xff0c;要注意的是&＃xff0c;本题的递归结束条件仍然是 temp 的长度与 nums 一样。

这个区别就体现在把原本放到递归结束条件的 if 判断中的 result.push([...temp]) 移到了 if 判断外面&＃xff1a;

// 全排列中的递归结束条件语句部分
...
if(temp.length &＃61;&＃61;&＃61; nums.length) {result.push([...temp]);return;
}
...// 本题的递归结束条件语句部分
...
result.push([...temp]);
if(temp.length &＃61;&＃61;&＃61; nums.length) {return;
}
...


这样就能保证每种长度的子集都能被存入 result 中。但是如果只在全排列的基础上改变这一个地方的话&＃xff0c;所得的结果如下&＃xff08;假设 nums&＃61;[1,2,3]&＃xff09;&＃xff1a;

// 只改变result.push([...temp])语句的位置所得结果
[[],[1],[2],[3],[1,2],[1,3],[2,3], [2,1],[3,1],[3,2],[1,2,3], [1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

// 预期结果
[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

注意上面标红部分就是重复得到的结果。所以说&＃xff0c;只改变上面所说的那一处的话是不能保证结果中没有重复的子集的。于是乎&＃xff0c;根据之前做的那道【LeetCode22】的经验&＃xff0c;我想应该还是要在生成 temp 时就对某些重复的结果进行筛选&＃xff0c;也就是要对 for 循环中那个 if 判断做点手脚。这也就是所谓的 “枝剪”操作。

具体需要对那个 if 判断做如下改动&＃xff1a;

// 原先写法
if(used[i]) {continue;
}// 增改如下
if(used[i] || (i>0 && used.slice(0, i&＃43;1).some(cur &＃61;> cur))) {continue;
}


而上面的 i>0 && used.slice(0, i&＃43;1).some(cur &＃61;> cur) 这个判断条件就是用于判断当前遍历元素 nums[i] 之前的元素是否被使用过。

只要 nums[0] ~ nums[i-1] 其中的任意一个元素之前被用过&＃xff0c;那就说明 result 中已经有了相关的子集了&＃xff0c;于是就要停止往下递归&＃xff0c;否则就会生成重复的子集。

其实一开始我没有用 slice(0, i&＃43;1)&＃xff0c;而是直接 used.some(cur &＃61;> cur)&＃xff0c;后来发现结果少了某些值才反应过来不应该直接对 used 中的所有元素做判断&＃xff0c;而应该取前 i-1 个元素做判断。

这里利用了一个很方便的Javascript数组方法&＃xff1a;Array.prototype.some()&＃xff0c;相关的用法描述可看下方的MDN文档&＃xff1a;

参考&＃xff1a;Array.prototype.some() - Javascript | MDN

除去上面提到的两个不同点&＃xff0c;其他的思路和那个【LeetCode46.全排列】的思路一模一样&＃xff0c;这里就不再赘述相关的思路了。

与本题相关的其他解释请看下方注释&＃xff1a;

/*** &＃64;param {number[]} nums* &＃64;return {number[][]}*/
var subsets &＃61; function(nums) {let result &＃61; [];let temp &＃61; [];backtracking(nums, []);return result;function backtracking(nums, used) {result.push([...temp]);// 把上面的语句从下面的if判断中提了出来&＃xff0c;这样就能保证每种长度的子集都能被捕获【tag1】if(temp.length &＃61;&＃61;&＃61; nums.length) {return;}for(let i &＃61; 0; i < nums.length; i&＃43;&＃43;) {// 不仅要判断当前元素是否在上一层递归中用过&＃xff0c;还要判断之前的元素是否有被用过的// 只要有一个被用过&＃xff0c;就不能再对其进行递归&＃xff0c;【tag2】if(used[i] || (i>0 && used.slice(0, i&＃43;1).some(cur &＃61;> cur))) {continue;}temp.push(nums[i]);used[i] &＃61; true;backtracking(nums, used);used[i] &＃61; false;temp.pop(nums[i]);}}
};提交记录
10 / 10 个通过测试用例
状态&＃xff1a;通过
执行用时&＃xff1a;80 ms, 在所有 Javascript 提交中击败了46.93%的用户
内存消耗&＃xff1a;40.3 MB, 在所有 Javascript 提交中击败了5.01%的用户
时间&＃xff1a;2021/09/25 15:23


上面的程序&＃xff0c;除了【tag1】和【tag2】两处&＃xff0c;其他地方都和之前的全排列题目一模一样。注意对照思考。

官方题解

更新&＃xff1a;2021年7月29日18:43:21

因为我考虑到著作权归属问题&＃xff0c;所以【官方题解】部分我不再粘贴具体的代码了&＃xff0c;可到下方的链接中查看。

更新&＃xff1a;2021年9月25日15:25:24

参考&＃xff1a;子集 - 子集 - 力扣&＃xff08;LeetCode&＃xff09;

【更新结束】

有关参考

更新&＃xff1a;2021年9月25日15:25:39
参考&＃xff1a;【算法-LeetCode】46. 全排列&＃xff08;回溯算法初体验&＃xff09;_赖念安的博客-CSDN博客
参考&＃xff1a;【算法-LeetCode】22. 括号生成&＃xff08;回溯&＃xff1b;有重复元素的全排列&＃xff09;_赖念安的博客-CSDN博客
参考&＃xff1a;Array.prototype.some() - Javascript | MDN
参考&＃xff1a;Array.prototype.slice() - Javascript | MDN