菜鸡刷算法的一天，每天分享两题算法，大家有这个想法的，可以给我个关注，然后一起坚持每天的算法之旅。希望我们共同进步，一起加油。 LC 78. 子集 给你一个整数数组 nums ，数
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
解题思路：使用 递归 + 回溯，将每一个种可能遍历一遍，符合条件，就放进输出数组中。
代码：
var subsets = function(nums) {
const res = [], path = [];
backstracking(0);
return res;
function backstracking(startIndex) {
res.push(path.slice());
for(let i = startIndex; i < nums.length; i++) {
path.push(nums[i])
backstracking(i + 1)
path.pop()
}
}
};
LC
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列
示例 1：
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
解题思路：在 子集 的基础上，增加了排序和去重操作
代码：
var subsetsWithDup = function(nums) {
const res = [], path = [];
let sortNums = nums.sort((a, b) => a - b) //先排序
backtracking(0, sortNums);
return res;
function backtracking(startIndex, sortNums) {
res.push(path.slice());
if(startIndex > nums.length - 1) return
for(let i = startIndex; i < nums.length; i++) {
if(i > startIndex && nums[i] === nums[i - 1]) continue; // 去重
path.push(nums[i]);
backtracking(i + 1, sortNums);
path.pop()
}
}
};