Original link: leetcode-cn.com/problems/pe…

Answer:

This problem is an advanced version of 47. Full permutation II, on which the need to filter out non-repeated permutation is added. If you are not familiar with the solution of 47. Complete permutation II, you can check my problem solving LeetCode problem solving: 46. Full permutation, backtracking, JavaScript, detailed comments.

  1. Use DFS to generate all possible permutations.
  2. You need to use the Used array to identify whether each value in NUMS has been used.
  3. Points to note in clearing state:
    • Since the permutation and Used variables are reused in each recursion, care needs to be taken to restore the current state after each recursion.
    • Assuming the first-level recursion, the permutation obtained each time after the state was clear in the for loop was respectively[1],[2].[3], used are respectively[true, false, false],[false, true, false],[false, false, true].
    • That is, when permutation is [2], all possible permutations from the previous loop have been output, and all used states of NUMS have been cleared, leaving the current recursion unaffected.
  4. Attention points for filtering repeated permutations:
    • Nums are sorted to ensure the continuity of each number and not repeated after a number is judged.
    • When iterating over a number in recursion, to[1, 1, 2]For example, only after traversing to the second1, the corresponding permutation will be adopted, and all previous permutations will be filtered out.
  5. When the recursion terminates, since permutation is only a reference, meaning its value changes as the function runs, it needs to be copied, otherwise the final output will be[]
function recursion(nums, result, permutation, used) {
  // 1. Recursive termination condition
  Exit the loop when the result of the permutation reaches the length of the original sequence
  if (permutation.length === nums.length) {
    // To save the current mutation to the result, you need to copy the original array, otherwise the permutation will be cleared after the for loop ends
    result.push(permutation.slice());
    return;
  }

  // Use loops to generate different permutations
  // Assuming the first-level recursion, permutation obtained in each for loop was [1], [2], [3] respectively.
  // The next level of recursion continues on the basis of the first level
  // As we enter each level of recursion, we do not know the arrangement of the previous level, so we can only perform traversal lookup.
  for (let i = 0; i < nums.length; i++) {
    // 2. The recursive logic of the current layer
    // If the current value is already in use, it cannot be sorted and can be skipped
    // The net effect is that the current value is only used when it is traversed for the last time.
    if (
      used[i] || // If the current value is already sorted
      // Since nums is repeatable, the current nums may have been arranged even if used[I] is false
      // If two adjacent words are equal, the current value may have already been arranged in the recurrence of the previous value
      (nums[i] === nums[i - 1] && used[i - 1]) // Determine if the previous value has been sorted
    ) {
      continue;
    }
    // The current value is sorted, identified in the used field
    used[i] = true;
    // Put the current value into the array
    permutation.push(nums[i]);
    // You can print the current arrangement here to help understand
    // console.log(result, permutation, used);

    // 3. Drill down to the next level of recursion
    // Note that this is depth-first traversal, which means that the final result of a permutation has been processed after recursion
    recursion(nums, result, permutation, used);

    // 4. Restore the current layer status
    // After the current value is used, empty the used value for the next for loop
    used[i] = false;
    // Eject the currently used value from permutation to avoid the next iterationpermutation.pop(); }}/ * * *@param {number[]} nums
 * @return {number[][]}* /
var permuteUnique = function (nums) {
  let result = []; // Store the result
  let permutation = []; // Store the result of each permutation
  let used = new Array(nums.length).fill(false); // Use the Boolean value corresponding to index to identify whether each numS value is used
  nums.sort((a, b) = > a - b); // Sort nums to ensure correct de-duplication

  // generate full permutation recursively
  recursion(nums, result, permutation, used);
  return result;
};
Copy the code