Full arrangement ii[duplicate removal of the same elements + standard backtracking]

Preface

For the full permutation problem , It is generally used DFS Enumerate （ Standard backtracking ）, And when there are duplicate elements in the array , You'll find repeated sets .
How to go heavy , Put equal elements together （ Sortable ）, And then through pre and cur Are they the same? , So as to come and go again .

One 、 Full Permutation II

Two 、 Put the elements together + Standard backtracking

package everyday.medium;

import java.util.*;

//  Full Permutation II
public class PermuteUnique {
    
    public List<List<Integer>> permuteUnique(int[] nums) {
    
        //  Prioritize , Place consecutive numbers next to each other , To cooperate pre To and fro .
        Arrays.sort(nums);

        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> el = new ArrayList<>();
        // Set  Record which numbers have been used .
        Set<Integer> set = new HashSet<>();
        // dfs The search method is full arrangement .
        dfs(nums, el, ans, set);
        //  return dfs After filling list
        return ans;
    }

    private void dfs(int[] nums, List<Integer> el, List<List<Integer>> ans, Set<Integer> set) {
    
        //  When every element is selected , Take it and arrange it , Then add the arrangement to list in .
        if (el.size() == nums.length) {
    
            ans.add(new ArrayList<>(el));
            return;
        }
        //  Standard backtracking 
        //  duplicate removal , When two different numbers are selected in this position , And when these two numbers are equal , Produce repetition .
        int pre = 1 << 31;
        for (int i = 0; i < nums.length; i++) {
    
            //  The two elements currently selected are the same  |  This element has been selected , Then pass .
            if (pre == nums[i] || set.contains(i)) continue;
            //  Standard backtracking 
            el.add(nums[i]);
            set.add(i);
            dfs(nums, el, ans, set);
            set.remove(i);
            el.remove(el.size() - 1);
            //  to update pre For the currently selected element , Prepare for the following choices .
            pre = nums[i];
        }
    }
}

summary

1） Standard backtracking
2） By putting the elements together , Combined with pre and cur Whether the variables are equal to achieve the goal of de duplication .

reference

[1] LeetCode Full Permutation II