如何解决力扣JS题目78和90的子集问题？
- 内容介绍
- 文章标签
- 相关推荐
本文共计624个文字，预计阅读时间需要3分钟。
菜鸡刷算法的一天，每天分享两题算法题，大家有这个想法的，可以给我个关注，然后一起坚持下去，每天的算法之旅。希望我们共同进步，一起加油！+LC+78.+子集+给你一个整数数组+nums+，给你一个整数+target+，请你找出该+nums+中所有和为+target+的+子集+。
菜鸡刷算法的一天，每天分享两题算法，大家有这个想法的，可以给我个关注，然后一起坚持每天的算法之旅。希望我们共同进步，一起加油。 LC 78. 子集给你一个整数数组 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 90. 子集 II给你一个整数数组 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() } } };
本文共计624个文字，预计阅读时间需要3分钟。
菜鸡刷算法的一天，每天分享两题算法题，大家有这个想法的，可以给我个关注，然后一起坚持下去，每天的算法之旅。希望我们共同进步，一起加油！+LC+78.+子集+给你一个整数数组+nums+，给你一个整数+target+，请你找出该+nums+中所有和为+target+的+子集+。
菜鸡刷算法的一天，每天分享两题算法，大家有这个想法的，可以给我个关注，然后一起坚持每天的算法之旅。希望我们共同进步，一起加油。 LC 78. 子集给你一个整数数组 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 90. 子集 II给你一个整数数组 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() } } };