78.M 子集

Problem: 78. 子集

思路

思路1：回溯法

• 核心思想：通过递归遍历每个元素的 “选” 与 “不选” 状态，生成所有可能的子集组合。

• 状态定义：

  • path：存储当前递归路径上已选择的元素。

  • start：当前遍历的起始索引，避免重复选择前面的元素（如选了 1 后，后续只能从 2 开始选，避免生成 [1,1]）。

• 递归流程：

  • 记录当前状态：每次进入递归时，先将当前path深拷贝后存入结果集（包括空集）。

  • 选择元素：从start开始遍历数组，依次选择当前元素加入path，并递归处理下一层（起始索引为i+1）。

  • 回溯：递归返回后，移除最后一个元素，尝试其他组合。

  • 时间复杂度：O (n×2ⁿ)，生成 2ⁿ个子集，每个子集拷贝需 O (n)。

思路2：位运算枚举法

• 核心思想：利用二进制掩码（mask）表示元素的选择状态，每一位代表对应索引的元素是否被选中。所有掩码处理完后，得到所有子集。

• 时间复杂度：O (n×2ⁿ)，枚举 2ⁿ个掩码，每个掩码检查 n 位。

Code

代码1：

func subsetsV1(nums []int) [][]int {
	var ans [][]int                // 存储最终的所有子集
	var path []int                 // 存储当前递归路径上的元素
	backtrace(nums, 0, path, &ans) // 从索引 0 开始回溯
	return ans
}

func backtrace(nums []int, start int, path []int, ans *[][]int) {
	// 将当前路径的深拷贝加入结果集（避免后续修改影响已加入的路径）
	*ans = append(*ans, append([]int{}, path...))

	// 从 start 开始遍历剩余元素，避免重复组合
	for i := start; i < len(nums); i++ {
		// 选择当前元素
		path = append(path, nums[i])
		// 递归处理下一个元素（注意这里传入的是 start+1，导致错误）
		backtrace(nums, i+1, path, ans)
		// 回溯：撤销选择，移除最后一个元素，尝试其他可能性
		path = path[0 : len(path)-1]
	}
}

代码2：

func subsets(nums []int) [][]int {
	var ans [][]int
	for mask := 0; mask < 1<<len(nums); mask++ {
		var set []int
		for i := 0; i < len(nums); i++ {
			if mask>>i&1 == 1 {
				set = append(set, nums[i])
			}
		}
		ans = append(ans, set)
	}
	return ans
}