LeetCode 47. 全排列 II

Categories:

Tags:

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

题目描述

✅ 47. 全排列 II

思路分析

回溯算法

参考代码

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) {
			res = append(res, append([]int{}, path...))
			return
		}
		for i := 0; i < len(nums); i++ {
			if used[i] {
				continue
			}
			if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
				continue
			}

			path = append(path, nums[i])
			used[i] = true

			backtrack()

			path = path[:len(path)-1]
			used[i] = false
		}
	}
	backtrack()
	return res
}

func permuteUnique(nums []int) [][]int {
	var res [][]int
	var path []int                  // 存放当前排列路径
	used := make([]bool, len(nums)) // 标记每个数字是否被使用过

	// 排序，保证重复的数字相邻
	sort.Ints(nums)

	var dfs func()
	dfs = func() {
		// 如果当前路径长度等于 nums 长度，说明找到了一个完整排列
		if len(path) == len(nums) {
			res = append(res, append([]int{}, path...))
			return
		}

		// 遍历每一个数字
		for i := 0; i < len(nums); i++ {
			// 如果当前数字已被使用，跳过
			if used[i] {
				continue
			}
			// 如果当前数字和前一个数字相同，且前一个数字未被使用，跳过（去重）
			if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
				continue
			}

			// 做选择
			path = append(path, nums[i])
			used[i] = true

			// 进入下一层递归
			dfs()

			// 回溯，撤销选择
			path = path[:len(path)-1]
			used[i] = false
		}
	}

	dfs()
	return res
}

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

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