思路
递归的本质是对一棵树中符合条件的节点进行收集，组合问题和分割问题都是收集树的叶子节点，而子集问题是收集树的所有节点。
子集也是一种组合问题，因为它的集合是无序的，子集 {1, 2} 和子集 {2, 1} 是一样的。所以在写递归的时候，取过的元素就不会重复取， for 就要从 start 开始，而不是从 0 开始。
当然，对于排列问题来说，for 就要从 0 开始，因为集合是有序的，取过的元素可以重复取，{1, 2} 和 {2, 1} 是两个集合。
回溯三部曲
- 递归函数参数
全局变量数组 path 为子集收集元素，二维数组 result 存放子集组合，递归函数需要 start 参数。
代码如下：
path []int
result [][]int
func dfs(nums []int, start int){}- 递归终止条件
我们知道递归问题中当遍历树节点时遇到叶子节点就需要终止递归。
问：那么如何判断是否到叶子节点呢？
答：到达叶子节点就意味着从数组 nums 中取元素取到没有元素为止，此时就是叶子节点。判断依据是当 start 已经大于等于数组的长度时，就说明此时没有元素可取了，到达了叶子节点。
代码如下：
if start >= len(nums) {
return
}其实这道子集问题不需要加终止条件，因为我们要收集所有的节点情况，收集的代码逻辑在终止条件之前，而且终止条件内不需要做任何逻辑操作，只需要 return 终止即可。其实，如果 start >= len(nums) 时，在 for 循环中不满足 i < len(nums)，该层 for 循环也就结束了，不需要手动 return 结束。但为了回溯三部曲的格式化，这里还是加上递归终止代码。
加上收集节点的代码如下：
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
if start >= len(nums) {
return
}- 单层搜索逻辑
子集问题与组合问题、分割问题最大的不同是不需要任何剪枝操作，因为子集问题就是要收集整棵树的所有节点。
代码如下：
for i := start; i < len(nums); i++ {
path = append(path, nums[i])
dfs(nums, i+1)
path = path[:len(path)-1]
}- 时间复杂度：O(n*2^n)
- 空间复杂度：O(n)
完整代码如下：
var (
path []int
result [][]int
)
func subsets(nums []int) [][]int {
path = []int{}
result = [][]int{}
dfs(nums, 0)
return result
}
func dfs(nums []int, start int) {
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
if start >= len(nums) {
return
}
for i := start; i < len(nums); i++ {
path = append(path, nums[i])
dfs(nums, i+1)
path = path[:len(path)-1]
}
}
思路
子集II 与 子集最大的区别就是数组中存在重复元素，最终子集结果要去重。
在组合问题中的 40.组合总和II 中有涉及，采用 used 数组执行树层去重的逻辑。注意去重一定要先对集合排序。
虽然树层去重的逻辑相同，但本题作为子集问题，需要改动的是不需要进行剪枝，收集节点也是在递归终止条件之前。
- 时间复杂度：O(n*2^n)
- 空间复杂度：O(n)
完整代码如下：
var (
path []int
result [][]int
used []bool
)
func subsetsWithDup(nums []int) [][]int {
path = []int{}
result = [][]int{}
used = make([]bool, len(nums))
sort.Ints(nums)
dfs(nums, 0)
return result
}
func dfs(nums []int, start int) {
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
if start >= len(nums) {
return
}
for i := start; i < len(nums); i++ {
if i > 0 && nums[i-1] == nums[i] && used[i-1] == false {
continue
}
path = append(path, nums[i])
used[i] = true
dfs(nums, i+1)
path = path[:len(path)-1]
used[i] = false
}
}
思路
本题是对数组集合取出所有的有序子集，同时数组中存在重复元素，要求结果不能有相同的子集。
涉及子集问题还有重复元素去重逻辑，本题与 90.子集II 很像，但是也有很大差别。
在 90.子集II 中是通过手动对数组排序 sort.Ints(nums) 然后再加一个 bool 类型的 used 数组来达到数层去重的目的。但是本题求递增子序列，不能对原有数组进行排序，所以之前的方法失效了。
本题需要重新思考，重新设计如何对同层节点去重。不能排序的树层去重。
参考代码随想录给出的树形结构图：代码随想录-491.非递减子序列
回溯三部曲
- 递归函数参数
子集问题，同一个元素不能重复使用，需要 start 参数用来表示下一层递归的起始位置。
代码如下：
path []int
result [][]int
func dfs(nums []int, start int){}- 终止条件
与子集问题一样，本题也要遍历树的每一个节点，在 start >= len(nums) 时遇到叶子节点，递归终止。当然，也可以不加终止条件。
在终止条件之前需要收集符合条件的子集结果，条件就是子集元素至少有两个。
代码如下：
if len(path) >= 2 {
temp := make([]int, len(nums))
copy(temp, path)
result = append(result, temp)
}
if start >= len(nums) {
return
}- 单层搜索逻辑
同一树层的节点中不能使用之前用过的元素。先看代码，然后做讲解。
代码如下：
used := make(map[int]bool, 201)
for i := start; i < len(nums); i++ {
if used[nums[i]] {
continue
}
if len(path) == 0 || nums[i] >= path[len(path)-1] {
path = append(path, nums[i])
used[nums[i]] = true
dfs(nums, i+1)
path = path[:len(path)-1]
}
}关键点
- used的作用域：我们在前面解决树层去重时都是定义的全局 used，而这里 used 在 for 循环之前定义，目的是确保它只影响当前层级的重复元素，而不会影响递归调用。在每次递归调用时 dfs 时都会重新创建 used，确保不同层级之间的递归不会互相干扰。
- 符合条件的元素：一个是当前负责收集结果的子集 path 没有元素；另一个是当前 path 非空，需要判断元素 nums[i] >= path[len(path)-1] 确保子序列是非递减的。
- 不重置 used[nums[i]] = false：在回溯时，不需要设置 used[nums[i]] = false，因为 used 的作用域仅限于当前层级，当调用 dfs 函数递归进入下一层时会重新创建新的 used。
注意点
- used 为什么不定义为一个数组，而是定义为一个 map 类型：因为题目中提到 -100 <= nums[i] <= 100，定义为数组下标不能为负数，而 map 类型的 key 是 int 类型，可以为负数。
- 定义的 used 初始化的大小为什么是 201：因为 -100 <= nums[i] <= 100，也就是说最多有 201 个数字需要记录，执行树层去重。
复杂度分析
- 时间复杂度：O(n*2^n)
- 空间复杂度：O(n)
完整代码如下：
var (
path []int
result [][]int
)
func findSubsequences(nums []int) [][]int {
path = []int{}
result = [][]int{}
dfs(nums, 0)
return result
}
func dfs(nums []int, start int) {
if len(path) >= 2 {
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
}
if start >= len(nums) {
return
}
used := make(map[int]bool, 201)
for i := start; i < len(nums); i++ {
if used[nums[i]] {
continue
}
if len(path) == 0 || nums[i] >= path[len(path)-1] {
path = append(path, nums[i])
used[nums[i]] = true
dfs(nums, i+1)
path = path[:len(path)-1]
}
}
}
No responses yet