题目:
难度:Middle
相关话题:数组
、回溯算法
给定一个可能包含重复元素的整数数组 nums ,返回该数组所有可能的子集(幂集)。
说明: 解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
思路:
由于输入含有重复值,因此需要排序并且通过if(i>start && nums[i]===nums[i-1])continue)
去重。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function(nums) {
let result=[],temp=[]
nums.sort()
backtrack(result,0,temp,nums)
return result
function backtrack(result,start,temp,nums){
result.push(temp.slice())
for(let i=start;i<nums.length;i++){
if(i>start && nums[i]===nums[i-1])continue
temp.push(nums[i])
backtrack(result,i+1,temp,nums)
temp.pop()
}
}
};
扩展阅读: