leetcode47（全排列II：回溯+哈希去重）

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

题解：这是一道枚举+组合的题目，可以用回溯法得到所有的组合情况，只不过序列中存在重复数字，我们需要哈希表来达到去重的目的，具体的做法就是用哈希表记录序列中每个数字的重复个数作为该数字可出现的次数，回溯的过程中要实时更新哈希表，如果回溯的过程中选择了某个数字，则将这个数字在哈希表中对应的可出现次数减1，如果该数字的可出现次数的值变为0，则不能再选择该数字。

class Solution {
    Stack<Integer>stack=new Stack<>();List<List<Integer>>res=new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {
    Map<Integer,Integer>map=new HashMap<>();for(int x:nums){
    map.put(x,map.getOrDefault(x,0)+1);}Set<Integer>keySet=map.keySet();backTrace(map,keySet, nums.length);return res;}private void backTrace(Map<Integer,Integer>map,Set<Integer>keySet,int len){
    if (stack.size()==len){
    res.add(new ArrayList<>(stack));return;}for(int x:keySet){
    if(map.get(x)>0){
    map.put(x,map.get(x)-1);stack.push(x);backTrace(map,keySet,len);stack.pop();map.put(x,map.get(x)+1);}}}
}