题目描述
给你一个整数数组 nums
,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入: nums = [1,2,3]
输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入: nums = [0]
输出: [[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums
中的所有元素 互不相同
代码及注释
func subsets(nums []int) [][]int {
// 初始化结果集和当前路径
res, path := make([][]int, 0), make([]int, 0)
// 定义深度优先搜索函数
var dfs func(nums []int, start int)
dfs = func(nums []int, start int) {
// 将当前路径复制到临时变量tmp中,并添加到结果集中
tmp := make([]int, len(path))
copy(tmp, path)
res = append(res, tmp)
// 遍历数组nums,从start位置开始
for i := start; i < len(nums); i++ {
// 将nums[i]添加到路径中
path = append(path, nums[i])
// 递归调用dfs函数,起始位置为i+1
dfs(nums, i+1)
// 回溯,将最后一个元素从路径中移除
path = path[:len(path)-1]
}
}
// 调用dfs函数,起始位置为0
dfs(nums, 0)
return res
}
代码解释
初始化结果集和当前路径
res, path := make([][]int, 0), make([]int, 0)
res
用于存储所有找到的子集。path
用于临时存储当前的子集。
定义深度优先搜索函数
var dfs func(nums []int, start int)
定义一个内部的递归函数 dfs
,用于执行深度优先搜索。
复制当前路径到临时变量,并添加到结果集中
tmp := make([]int, len(path))
copy(tmp, path)
res = append(res, tmp)
这里的目的是为了保留 path
的原始内容,因为在后续的递归调用中,path
的内容会被修改。通过将 path
的内容复制到 tmp
,可以保证在添加到 res
中的是当前的完整子集。
遍历数组,生成所有可能的子集
for i := start; i < len(nums); i++ {
path = append(path, nums[i])
dfs(nums, i+1)
path = path[:len(path)-1]
}
for i := start; i < len(nums); i++
:从start
位置开始遍历数组nums
。path = append(path, nums[i])
:将当前遍历的元素nums[i]
添加到路径path
中。dfs(nums, i+1)
:递归调用dfs
函数,从下一个位置i+1
开始。path = path[:len(path)-1]
:回溯,将最后一个添加到path
的元素移除。
通过以上步骤,可以确保找到数组 nums
的所有可能子集,并将它们添加到结果集 res
中。
使用深度优先搜索的思想,通过递归遍历数组 nums
的所有可能组合,以找到所有的子集。在这个过程中,使用 path
来记录当前的子集,并通过回溯的方式来实现遍历和搜索的过程。
本文含有隐藏内容,请 开通VIP 后查看