回溯
解题思路
全局变量数组 path 为子集收集元素，二维数组 res 存放子集组合；
比较子集（数组）的异同非常耗时，需要先 排序数组 ，再比较数组中每个元素的异同，
重复子集剪枝：
- 分支 1：如果第一轮选择了 2 ，第二轮选择了 3 ，则记为 [2,3,XX]；
- 分支 2：如果第一轮选择了 3 ，第二轮选择了 2 ，则记为 [3,2,XX] ，那这样就会出现重复集合，第二轮应该跳过 2，从 3 开始；
解决步骤二的问题，可以定义一个 startIndex 索引，每次递归传入 startIndex 索引，这样就可以跳过前面的索引，避免重复集合；
剪枝：减掉同一层相邻重复元素；
图解
复杂度
-
时间复杂度：
O(n*2^n)，一共 2^n 个状态，每种状态需要O(n)的时间来构造子集； -
空间复杂度：
O(n)，临时数组 t 的空间代价是O(n)，递归时栈空间的代价为O(n)；
实现代码
var subsetsWithDup = function (nums) {
let res = [];
nums.sort((a, b) => a - b);
backtrack(res, nums, 0, []);
return res;
};
const backtrack = (res, nums, startIndex, path) => {
res.push([...path]);
for (let i = startIndex; i < nums.length; i++) {
if (i > startIndex && nums[i] === nums[i - 1]) continue;
path.push(nums[i]);
backtrack(res, nums, i + 1, path);
path.pop();
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 78. 子集
上一篇
评论
