题解 | #有重复项数字的全排列#

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if (num.length == 0) {
            return list;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : num) {
            if (map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            } else {
                map.put(i, 1);
            }
        }
        getList(map, list, new ArrayList<>(), num.length);
        Collections.sort(list, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                for (int i = 0; i < o1.size(); i++) {
                    if (o1.get(i) > o2.get(i)) {
                        return 1;
                    } else if (o1.get(i) < o2.get(i)) {
                        return -1;
                    }
                }
                return 0;
            }

            @Override
            public boolean equals(Object obj) {
                return false;
            }
        });
        return list;


    }

    public void getList(Map<Integer, Integer> map,
                        ArrayList<ArrayList<Integer>> list, ArrayList<Integer> result, int size) {
        if (result.size() == size) {
            list.add(new ArrayList<>(result));
        }
        for (int num : map.keySet()) {
            result.add(num);
            Map<Integer, Integer> map1 = new HashMap<>(map);
            if (map1.get(num) > 1) {
                map1.put(num, map1.get(num) - 1);
            } else {
                map1.remove(num);
            }

            getList(map1, list, result, size);
            result.remove(result.size() - 1);

        }


    }

}

回溯算法。这个问题和有重复的很像，但是为了保证取值为O(1)，因此才用了map

1、原来池子里有1,1,2

map={1:2,2:1}

2、取出1个1

则池子里还有map={1:1,2:0}

直到池子中的数据被取完，则回溯回去