当前位置：首页 > article >正文

LeetCode：47.全排列 II

article 2025/1/20 2:18:42

跟着carl学算法，本系列博客仅做个人记录，建议大家都去看carl本人的博客，写的真的很好的！
代码随想录

LeetCode：47.全排列 II
给定一个可包含重复数字的序列 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]]

使用了used数组进行去重逻辑的判断，需要注意for循环里面的两个if

	public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtracking(nums, used, new ArrayList(), res);
        return res;
    }

    private void backtracking(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // [1,1,2]中以第一个1开头之后，第二个1就不需要了，需要剪枝
            if (i >= 1 && nums[i] == nums[i - 1] && !used[i - 1])
                continue;
            // [1,1,2]中第一个数字取了第一个1之后，递归进行取第二个数的时候，需要排除第一个1
            if (used[i])
                continue;
            path.add(nums[i]);
            used[i] = true;
            backtracking(nums, used, path, res);
            path.removeLast();
            used[i] = false;
        }
    }