LeetCode 47. 全排列 II

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 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]]

提示：

1 <= nums.length <= 8

-10 <= nums[i] <= 10

思路分析

这道题目要求我们生成所有不重复的全排列。由于输入数组中可能包含重复元素，我们需要在生成排列时避免重复。我们可以使用回溯算法来解决这个问题，并在递归过程中通过排序和跳过重复元素来避免生成重复的排列。

具体步骤如下：

对数组进行排序，以便我们可以轻松地跳过重复元素。

使用一个布尔数组 used 来记录哪些元素已经被使用过。

在回溯过程中，如果当前元素与前一个元素相同且前一个元素未被使用，则跳过当前元素以避免重复。

递归生成排列，并在递归结束后回溯。

参考代码

func permuteUnique(nums []int) [][]int {
	var res [][]int
	var path []int
	sort.Ints(nums) // 先对数组进行排序
	used := make([]bool, len(nums))

	var backtrack func()
	backtrack = func() {
		if len(path) == len(nums) {
			// 生成一个新的排列
			temp := make([]int, len(path))
			copy(temp, path)
			res = append(res, temp)
			return
		}

		for i := 0; i < len(nums); i++ {
			// 跳过已经使用过的元素
			if used[i] {
				continue
			}

			// 跳过重复元素
			if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
				continue
			}

			// 选择当前元素
			used[i] = true
			path = append(path, nums[i])

			// 递归生成下一个元素
			backtrack()

			// 回溯
			used[i] = false
			path = path[:len(path)-1]
		}
	}

	backtrack()

	return res
}

时间复杂度: O (n * n!)，其中 n 是数组的长度。生成所有排列的时间复杂度为 O (n!)，每个排列需要 O (n) 的时间来复制到结果中。

空间复杂度: O (n)，用于递归调用栈和布尔数组 used。

🍏 点击查看 Java 题解

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

    public void backtrack(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++) {
            if (used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backtrack(nums, used, path, res);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/25893218