This is the 14th day of my participation in the August More Text Challenge. For details, see:August is more challenging

preface

Question 47 full arrangement II is as follows:

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

Example 1:

Output: input: nums =,1,2 [1] [,1,2 [1], [1, 2, 1], [2,1,1]]Copy the code

Example 2:

Output: input: nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the code

A, thinking

This question is basically the same as the force question 46 – full permutation, the only difference is: the array may have repeated elements, need to return all not repeated full permutation

So how do you ensure that you don’t return duplicate values? There are mainly two points:

  • You cannot select the same elements in the current level of recursion: use sort + to avoid adding adjacent equal elements in the same level of recursion
  • You cannot select the same index twice: you cannot select a selected element in the next level of recursion

For example, nums = [1,1,2], the first recursion has already selected the first element nums[0]. When you backtrack again for the next iteration, nums[1] = 1 should not be selected to prevent the results from repeating

For example

Nums = [2,1,1] in example 1 is used as an example here

  1. First the arrayascending.nums = {1, 1, 2}
  2. i=0.nums[0] = 1Push, the value in the stack is1, and continue the next level of recursion
  3. Recursion 1: causei = 0Already selected, skip
  4. Recursive 1:i=1.nums[1] = 1Push, the value in the stack is1 - > 1, and continue the next level of recursion
  5. Recursion 2: causei = 0 和 i = 1Already selected, skip
  6. Recursive 2:i=2.nums[2] = 2Push, the value in the stack is1 -> 1 -> 2At this time,The stack is full, records the set of results, and pushes the stack out of the stack, the value in the stack is1 - > 1. Back up
  7. Recursion 1: the stack is pushed out of the stack and the value in the stack is1.i=2.nums[2] = 2Push, the value in the stack is1 - > 2, and continue the next level of recursion
  8. Recursion 2: causei = 0 和 i = 2Already selected, skip
  9. Recursive 2:i=1.nums[1] = 1Push, the value in the stack is1 -> 2 -> 1At this time,The stack is full, records the set of results, and pushes the stack out of the stack, the value in the stack is1 - > 2. Back up
  10. Recursion 1: the stack is pushed out of the stack and the value in the stack is1. The current layer traversal ends and backtraces upward
  11. The stack is pushed out of the stack. The stack is empty. Due to thei=1When,nums[1] == nums[0], so skip. (Adjacent elements in the same layer are equal)
  12. . , the follow-up process is basically the same
  13. Finally, the correct result set can be obtained:,1,2 [[1], [1, 2, 1], [2,1,1]]

Second, the implementation

The implementation code

The implementation code is consistent with the idea of using a HashMap to save the subscripts in the path

    /** * recursion */
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        Arrays.sort(nums);  // Arrange in ascending order
        dfs(ret, nums, stack, new HashMap<>());
        return ret;
    }

    public void dfs(List<List<Integer>> list, int[] nums, Stack<Integer> stack, Map<Integer, Object> map) {
        if (stack.size() == nums.length) {
            list.add(new ArrayList<>(stack));
            return;
        }
        for (int i=0; i<nums.length; i++) {
            int num = nums[i];
            if(map.containsKey(i) || (i ! =0 && num == nums[i-1] && map.containsKey(i-1)))
                continue; stack.push(num); map.put(i, num); dfs(list, nums, stack, map); stack.pop(); map.remove(i); }}Copy the code

The test code

public static void main(String[] args) {
    int[] nums = {2.1.1};
    new Number47().permuteUnique(nums);
}
Copy the code

The results of

Optimized version

The implementation code

Replacing the HashMap with a Boolean array of all variables is an effective way to improve efficiency

    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false; perm.remove(idx); }}Copy the code

The results of

Third, summary

Thank you for seeing the end, it is my great honor to help you ~♥