leetcode-78：子集

问题

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）
解集不能包含重复的子集。你可以按任意顺序返回解集

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

思路

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点

其实子集也是一种组合问题，因为它的集合是无序的

那么既然是无序，取过的元素不会重复取，写回溯算法的时候，**for**就要从**startIndex**开始，而不是从**0**开始

求排列问题的时候，for就要从0开始，因为集合是有序的，{1, 2}和{2, 1}是两个集合

以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：

从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合

回溯三部曲

• 递归函数参数

  • 全局变量数组path为子集收集元素，二维数组result存放子集组合。（也可以放到递归函数参数里）
  • 递归函数参数在上面讲到了，需要startIndex

    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    public void backtracking(int[] nums, int startIndex) {

• 递归终止条件

从图中可以看出：

剩余集合为空的时候，就是叶子节点

那么什么时候剩余集合为空呢？
就是startIndex已经大于数组的长度了，就终止了，因为没有元素可取了

if (startIndex >= nums.length) {
    return;
}

其实可以不需要加终止条件，因为**startIndex >= nums.length**，本层for循环本来也结束了

• 单层搜索逻辑

  • 求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树

    for (int i = startIndex; i < nums.length; i++) {
    path.add(nums[i]);    // 子集收集元素
    backtracking(nums, i + 1);  // 注意从i+1开始，元素不重复取
    path.remove(path.size() - 1);            // 回溯
    }
    

    class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    
    public void backtracking(int[] nums, int startIndex) {
       result.add(new ArrayList<Integer>(path)); // 收集子集
       if (startIndex >= nums.length) { 
           return;
       }
       for (int i = startIndex; i < nums.length; i++) {
       path.add(nums[i]);    
       backtracking(nums, i + 1);  
       path.remove(path.size() - 1);            
    }
    }
    
    public List<List<Integer>> subsets(int[] nums) {
       backtracking(nums, 0);
       return result;
    }
    }
    

    不写终止条件会不会无限递归？
    并不会，因为每次递归的下一层就是从i+1开始的