leetcode 47. Permutations II full permutations II (medium)

One 、 The main idea of the topic

label : Search for

https://leetcode.cn/problems/permutations-ii

Given a sequence that can contain repeating numbers nums , In any order Returns all non repeating permutations .
Example 1：

Input ：nums = [1,1,2]
Output ：
[[1,1,2],
[1,2,1],
[2,1,1]]

Example 2：

Input ：nums = [1,2,3]
Output ：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Tips ：

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

Two 、 Their thinking

Using backtracking method to solve the full permutation problem , There are duplicates of elements in the given array , Therefore, there will be repetition in the full permutation results after the backtracking method is used , As shown in the figure below .

resolvent , Construct a hashmap,key Is an element ,value Is the number of elements , And then use the backtracking method to solve it

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        //  Construct a hashmap
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int n : nums) {
            int count = countMap.getOrDefault(n, 0);
            countMap.put(n, count + 1);
        }
        dfs(countMap, nums.length, new LinkedList<>(), ans);
        return ans;
    }

    void dfs(Map<Integer, Integer> countMap, int total, Deque<Integer> perm, List<List<Integer>> ans) {
        //  Use a two terminal queue 
        if (perm.size() == total) {
            ans.add(new ArrayList<>(perm));
        }
        for (Map.Entry<Integer, Integer> tmp : countMap.entrySet()) {
            if (tmp.getValue() > 0) {
                int oldValue = tmp.getValue();
                perm.offerFirst(tmp.getKey());
                tmp.setValue(tmp.getValue() - 1);
                dfs(countMap, total, perm, ans);
                tmp.setValue(oldValue);
                perm.pollFirst();
            }
        }
    }
}

Four 、 Summary notes

• 2022/6/12 To record the type of results, use a double ended queue