LeetCode 90. 子集 II

Categories:

Tags:

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

题目描述

✅ 90. 子集 II

思路分析

回溯问题

参考代码

func subsetsWithDup(nums []int) [][]int {
	var res [][]int
	var path []int

	sort.Ints(nums)

	var backtrack func(start int)

	backtrack = func(start int) {
		res = append(res, append([]int{}, path...))

		for i := start; i < len(nums); i++ {
			if i > start && nums[i] == nums[i-1] {
				continue
			}

			path = append(path, nums[i])

			backtrack(i + 1)

			path = path[:len(path)-1]
		}
	}

	backtrack(0)

	return res
}

func subsetsWithDup(nums []int) [][]int {
	var res [][]int
	var path []int

	// 先排序，让重复元素相邻
	sort.Ints(nums)

	var backtrack func(start int)
	backtrack = func(start int) {
		// 每次递归都加入当前路径
		res = append(res, append([]int{}, path...))

		for i := start; i < len(nums); i++ {
			// 剪枝逻辑：跳过同一层中重复元素
			if i > start && nums[i] == nums[i-1] {
				continue
			}
			// 做选择
			path = append(path, nums[i])
			// 递归
			backtrack(i + 1)
			// 撤销选择
			path = path[:len(path)-1]
		}
	}

	backtrack(0)
	return res
}

时间复杂度：O(2^n)，虽然剪枝，但最坏情况下还是会生成 2^n 个子集。

空间复杂度：O(n)，递归栈深度最多为 n，path 最长为 n。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

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