原文:90. 子集 II(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址:https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-090/

题目:

难度: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()
    }
  }
};

扩展阅读: