子集（ LeetCode 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] <= 10nums中的所有元素 互不相同
二、题目解析
一般来说，回溯算法的思考步骤如下：
1、画出递归树，找到状态变量(回溯函数的参数)
2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
3、确定选择列表，即需要把什么数据存储到结果里面
4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
5、做出选择，递归调用该函数，进入下一层继续搜索
6、撤销选择，回到上一层的状态
翻译成代码为如下的形式，也就是回溯算法解题的一个模板：
// 1、画出递归树，找到状态变量(回溯函数的参数)
private void backtrack("原始参数") {
// 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
if ("终止条件") {
// 一些逻辑操作（可有可无，视情况而定）
// 比如，在 N 皇后问题中，在这一步把数据加入到了结果里面
添加操作
return;
}
// 3、确定选择列表，即需要把什么数据存储到结果里面
// for 循环就是一个选择的过程
for ("遍历本层集合中元素") {
// 一些逻辑操作（可有可无，视情况而定）
// 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
// 5、做出选择，递归调用该函数，进入下一层继续搜索
// 递归
backtrack("新的参数");
// 一些逻辑操作（可有可无，视情况而定）
// 6、撤销选择，回到上一层的状态
}
}
那么对于子集这道问题来说，我们按照模板进行一个思考：
1、画出递归树，找到状态变量(回溯函数的参数)
结合最终结果来画递归树。
2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件。
当访问的数组下标超过了 nums 数组的长度时，递归结束。
3、确定选择列表，即需要把什么数据存储到结果里面。
把本次递归访问的元素加入到 subset 数组中
4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
由于题目要求我们去存储所有的子集，也就意味着不存在丢弃的操作，也就不需要剪枝了。
5、做出选择，递归调用该函数，进入下一层继续搜索
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public List<List<Integer>> subsets(int[] nums) {
// 结果集合
List<List<Integer>> sets = new ArrayList<List<Integer>>();
// 每次的子集
List<Integer> subset = new ArrayList<Integer>();
// 执行回溯算法
backtrack( 0 , nums , subset , sets);
// 返回结果
return sets;
}
// i 表示递归时正在访问的数组元素下标
// nums 表示当前集合中的元素
// subset 表示每次递归后生成的子集，就是路径上的那些元素
// sets 表示最终生成的所有子集合
private void backtrack( int i , int[] nums , List<Integer> subset , List<List<Integer>> sets ){
// 每次确定好一个子集，都把它加入到结果集合中
sets.add(new ArrayList<Integer>(subset));
// 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
// 本题中可以不加这个判断，大家可以思考一下为什么可以不加，结合 for 循环的边界来思考
if( i >= nums.length){
return;
}
for( int j = i ; j < nums.length ; j++ ){
// 把本次递归访问的元素加入到 subset 数组中
subset.add(nums[j]);
// 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
// 本题不需要剪枝
// 5、做出选择，递归调用该函数，进入下一层继续搜索
// 递归
backtrack( j + 1 , nums , subset , sets);
// 6、撤销选择，回到上一层的状态
// 取消对 nums[i] 的选择
subset.remove(subset.size() - 1);
}
}
}
2、C++ 代码
3、Python 代码
四、复杂度分析
时间复杂度：O(n * 2 ^ n)。一共 2^n 个状态，每种状态需要 O(n) 的时间来构造子集。
空间复杂度：O(n)。临时数组 subsets 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。
