算法思想

这道题和算法基础课中的模板题很像，AcWing 842. 排列数字,只不过这道题有重复的数字，所以我们需要人为规定 重复的数字中，后面的数要比前面的数后放

1：排序，使得重复的数字安在一起
2：保证在重复的数中，一定是前一个数先放，后一个数再放，达到后面的数一定放在前面数的后面，使我们的结果是唯一的，否则在结果集中就会出现重复的结果;

java代码

class Solution {
    static List<List<Integer>> list = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();
    static boolean[] st;

    public List<List<Integer>> permutation(int[] nums) {
        st = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums);
        return list;
    }

    private static void dfs(int[] nums)
    {
        if(path.size() == nums.length)
        {
            list.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0; i < nums.length; i ++)
        {
            if(st[i] == true) continue;         //如果这一步已经走过了
            if(i > 0 && nums[i] == nums[i - 1] && st[i - 1] == false) continue; //保证重复的数,后放在前的后面
            st[i] = true;
            path.add(nums[i]);
            dfs(nums);
            path.remove(path.size() - 1);      //恢复现场
            st[i] = false;
        }
    }
}