全排列2

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

提示：

    1 <= nums.length <= 8
    -10 <= nums[i] <= 10

通过次数123,743
提交次数198,637

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> list = new ArrayList<>();

        for (int val : nums) {
            list.add(val);
        }

        backtrack(nums.length, list, 0);
        return result;
    }

    private List<List<Integer>> result = new ArrayList<>();
    public void backtrack(int n, List<Integer> tmpList, int start) {
        if (start == n) {
            if (!result.contains(tmpList)) {//去重
                result.add(new ArrayList<>(tmpList));
            }
            return;
        }
        for (int i = start; i < n; i++) {
            Collections.swap(tmpList, start, i);//交换元素
            backtrack(n, tmpList, start + 1);
            Collections.swap(tmpList, start, i);//换回来

        }
    }
}

要解决重复问题，我们只要设定一个规则，保证在填第 idx 个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」

if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
     continue;
 }

class Solution {
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}

参考文献

作者：LeetCode-Solution

赏

谢谢你请我吃糖果

微信