78. 子集

题目描述：

给你一个整数数组 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 中的所有元素 互不相同

---

解题分析及思路：

方法：回溯

思路：

1. 定义递归函数： 定义一个递归函数 dfs，该函数用于在当前选择的基础上继续搜索可能的组合。参数包括当前搜索起始位置 index、当前已选择的组合 res。
2. 递归搜索： 在 dfs 函数中，使用循环遍历候选数组 nums，从给定的 index 开始。对于每个候选数字 nums[i]，都将其加入到当前组合 res 中，并递归调用 dfs 函数继续搜索下一个数字。
3. 回溯操作： 在递归调用返回后，需要将刚加入的数字从当前组合 res 中移除，以便尝试其他可能的数字组合。
4. 结束条件： 当nums遍历完成之后，就代表已经结束
5. 返回结果： 最终将所有找到的组合存储在结果集 result 中，并在递归结束后返回结果集。

func subsets(nums []int) (result [][]int) {
	var dfs func(index int, res []int)
dfs = func(index int, res []int) {
		var ans = make([]int, len(res))
		copy(ans, res)
		result = append(result, ans)
		for i := index; i < len(nums); i++ {
			res = append(res, nums[i])
      dfs(i+1, res)
			res = res[:len(res)-1]
		}
	}
  dfs(0, []int{})
	return
}

复杂度：

• 时间复杂度：O(N * 2 ^N)
• 空间复杂度：O(N)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:2.3 MB,击败了45.65% 的Go用户