This is the 8th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

Given a sequence nums that can contain repeating numbers, return all non-repeating permutations in any order.

Example 1: input, output nums =,1,2 [1] : [,1,2 [1], [1, 2, 1], [2,1,1]]

Example 2: input, output nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]

Link: leetcode-cn.com/problems/pe…

Answer key

  1. The difference between this problem and LeetCode 46 Permutations lies in that the previous problem array does not contain repeated numbers, while this problem contains repeated numbers. If the solution of problem 46 is still followed, there will be a full and repeated arrangement. Therefore, the key to this problem is how to build on the solution of the last problem. Added deweighting operations. So, the first thing to think about is to use the JS data structure Set. The Set type guarantees that the elements in the Set are unique, but the point to note is that if the Set is an array, it can’t be repeated, it will think that the two arrays [1,1,2] and [1,1,2] are different elements. So we can first convert to string insert, and then solve to array. The specific code is as follows.
/ * * *@param {number[]} nums
 * @return {number[][]}* /
var permuteUnique = function(nums) {
    const n = nums.length
    let used = new Array(n).fill(0)
    let ansSet = new Set(a)const dfs = (nums, d, n, used, curr, ansSet) = > {
        if (d === n) {
            // Add to string
            ansSet.add(curr.join(', '))
            return
        }
        
        for (let i = 0; i < n; ++i) {
            if (used[i]) continue
            used[i] = 1
            curr.push(nums[i])
            dfs(nums, d + 1, n, used, curr, ansSet)
            used[i] = 0
            curr.pop()
        }
    }
    
    dfs(nums, 0, n, used, [], ansSet)
    
    // Convert Set to Array
    let ans = Array.from(ansSet)
        .map(item= > {
            let tmp = item.split(', ')
            return tmp.map(Number)})return ans
};
Copy the code
  1. A pruning operation. What does that mean? Which is that we’re going to skip the permutation that’s going to repeat in the recursion. How do you do that? There are two steps. The first step is to sort the array, so that the same elements are adjacent in the array; The second and most important step, when traversing the same element, is to skip the recursion if it is not the first element and the same element before it is not used. Why is this condition? For example, the first two combinations of [1, 1, 2] are [1, 1, 2], [1, 2, 1], and the next time we recurse, the array curr is [], and we recurse to the second 1, which is the subscript 1. If curr starts with that 1 again, It’s going to be repeated; Another condition is that the preceding element is not used. This is because when the preceding 1 is not used, the next 1 must be skipped because the preceding 1 already includes all combinations of 1s. See the code below.
/ * * *@param {number[]} nums
 * @return {number[][]}* /
var permuteUnique = function(nums) {
    const n = nums.length
    let path = []
    let res = []
    nums = nums.sort((a,b) = > a - b)
    let use = new Array(n).fill(0)
    
    const dfs = (d) = > {
      if (d === n) {
        res.push([...path])
        return
      }
      for (let i = 0; i < n; i++) {
        if (use[i]) continue
        if (i > 0 && nums[i] === nums[i-1] && !use[i-1]) continue
        path.push(nums[i])
        use[i] = 1
        dfs(d+1)
        use[i] = 0
        path.pop()
      }
    }
    
    dfs(0)
    return res
};
Copy the code