LeetCode 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

题意：全排序，但是已知的序列里面有重复的，找出所有不重复的全排序。

跟46题，也就是上一道题，比较相似，我们需要加一个限制条件，在递归的过程中，如果元素是一样的就不用重复的递归了。

java代码：

public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        //Arrays.sort(nums);
        dfs(list, nums, 0);
        return list;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private static void dfs(List<List<Integer>> list, int[] nums, int j) {
        if (j == nums.length) {
            for (int i = 0; i < nums.length; i++) {
                temp.add(nums[i]);
            }
            list.add(temp);
            temp = new ArrayList<>();
        }
        List<Integer> flags = new ArrayList<>();
        for (int i = j; i < nums.length; ++i) {
            if (!flags.contains(nums[i])) {
                flags.add(nums[i]);
                swap(nums, i, j);
                dfs(list, nums, j + 1);
                swap(nums, i, j);
            }
        }
    }