90.Subsets II

Given a collection of integers that might contain duplicates nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

Analyze

回溯法解组合问题。

• 1
• 1
  • 2
• 1
  • 2
    • 2
• 2
• 2
  • 2

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
  const result = []
  const sortedNums = nums.sort((r1, r2) => r1 - r2)
  iterator(sortedNums, 0, [], result)
  return result
};

var iterator = function(nums, start, temp, result) {
  result.push([...temp])

  for (let i = start; i < nums.length; i++) {
    if (nums[i] === nums[i - 1] && i !== start) { continue }
    temp.push(nums[i])
    iterator(nums, i + 1, temp, result)
    temp.pop(nums[i])
  }
}