Topic describes

Original title link: Subset II

Given an array of integers, nums, which may contain repeating elements, return all possible subsets (power sets) of that array.

The solution set cannot contain duplicate subsets. Returns a solution set in which subsets can be arranged in any order.

The sample

Enter: nums = [1.2.2] output: [[],[1], [1.2], [1.2.2], [2], [2.2]]
Copy the code

1 <= nums.length <= 10 -10 <= nums[i] <= 10

answer

This is a variant of leetcode-78. The subset is simply a condition that has no repeating elements but may contain repeating elements.

This kind of problem with the backtracking method to solve it is easier, here is a backtracking template commonly used by the author:

function backtracking(list) {
  const result = [] // Define the result collection array
  const temp = [] // Define auxiliary arrays or variables
  // Define an auxiliary function
  function helper(idx) {
    if{result.push([...temp]) {result.push([...temp])// Add the result collection array if it is a feasible solution
    }
    // Traverse the region to be searched based on the index
    for (let item of list.slice(idx)) {
      temp.push(item) // The auxiliary array changes state with the new member
      ifHelper (list.indexof (item) +1) // Search further if certain conditions are met
      }
      temp.pop() // return to the original state
    }
  }

  helper(0) // Call the helper function

  return result // Return the result
}
Copy the code

In the leetcode-78. Subset, since there is no repetition number, we can certainly continue to search further. Here is the solution to question 78:

var subsets = function (nums) {
  const res = []
  const tempRes = []
  // Start from index IDx
  const helper = idx= > {
    res.push([...tempRes])
    for (let i = idx; i < nums.length; i++) {
      tempRes.push(nums[i])
      helper(i + 1)
      tempRes.pop()
    }
  }
  helper(0)
  return res
}
Copy the code

However, in this case, since there may be repeated numbers, we need to judge whether the number is repeated when we continue to search. Here, we use sorting first and define a variable of Set type to save the auxiliary array into a string as a value in the Set. The recursive search continues only if the set does not contain the same value:

var subsetsWithDup = function (nums) {
  let res = []
  let tempRes = []
  let set = new Set()
  nums.sort((a, b) = > a - b)
  const helper = idx= > {
    res.push([...tempRes])
    for (let i = idx; i < nums.length; i++) {
      tempRes.push(nums[i])
      const value = tempRes.join(The '-')
      if(! set.has(value)) { set.add(value) helper(i +1)
      }
      tempRes.pop()
    }
  }
  helper(0)
  return res
}
Copy the code

Complexity analysis:

• Time complexity: sorting array complexity O(NlogN), recursive search in the worst case is no repeating elements in NUMS, it is necessary to enumerate all 2^n subsets, each subset to add a copy of the answer, time-consuming O(n), that is, complexity O(n * 2^n).