题目

image.png

思路

  • 与全排列类似，只是关键在于去重，但是其思想与组合总和 II的去重思想一致

  • dfs+回溯

    代码

    1.   public List<List<Integer>> permuteUnique(int[] nums) {
    2.       List<List<Integer>> res = new ArrayList<>();
    3.       Arrays.sort(nums);
    4.       dfs(nums, 0, res, new ArrayList<>());
    5.       return res;
    6.   }
    8.   public void dfs(int[] nums, int index, List<List<Integer>> res, List<Integer> tmp) {
    9.       if (nums.length == tmp.size()) {
    10.           res.add(new ArrayList<>(tmp));
    11.           return;
    12.       }
    13.       for (int i = index; i < nums.length; i++) {
    14.           //去重
    15.           if (nums[i] == -100 || i != index && nums[i] == nums[i - 1]) continue;
    16.           tmp.add(nums[i]);
    17.           nums[i] = -100;
    18.           dfs(nums, index, res, tmp);
    19.           nums[i] = tmp.remove(tmp.size() - 1);
    20.       }
    21.   }

    全排列 II