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

package org.example.test;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class BackTrackTest {
    public static void main(String[] args) {
        int[] test = {1, 1, 2};
        System.out.println(JSONObject.toJSONString(permuteUnique(test)));
    }

    static ArrayList<ArrayList<Integer>> ans = new ArrayList<>();

    /**
     * 回溯+去重+排序
     *
     * @param num
     * @return
     */
    public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        int len = num.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < num.length; i++) {
            map.put(i, num[i]);
        }
        ArrayList<Integer> track = new ArrayList<>();
        back(map, track);
        HashMap<String, ArrayList<Integer>> map1 = new HashMap<>();
        for (ArrayList<Integer> an : ans) {
            StringBuilder key = new StringBuilder();
            for (int j = 0; j < num.length; j++) {
                key.append(an.get(j));
            }
            map1.put(key.toString(), an);
        }
        ArrayList<ArrayList<Integer>> ans1 = new ArrayList<>();
        for (Map.Entry<String, ArrayList<Integer>> entry : map1.entrySet()) {
            ans1.add(entry.getValue());
        }
        ans1.sort(new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                StringBuilder key1 = new StringBuilder();
                StringBuilder key2 = new StringBuilder();
                for (int i = 0; i < len; i++) {
                    key1.append(o1.get(i));
                    key2.append(o2.get(i));
                }
                return key1.toString().compareTo(key2.toString());
            }
        });
        return ans1;
    }

    private static void back(Map<Integer, Integer> num, ArrayList<Integer> track) {
        if (track.size() == num.size()) {
            ArrayList<Integer> tmp = new ArrayList<>();
            for (Integer value : track) {
                tmp.add(num.get(value));
            }
            ans.add(tmp);
            return;
        }

        for (Map.Entry<Integer, Integer> entry : num.entrySet()) {
            Integer key = entry.getKey();
            if (track.contains(key)) {
                continue;
            }
            track.add(key);
            back(num, track);
            track.remove(track.size() - 1);
        }
    }
}