LeetCode 78：子集

链接
题目：

思路：回溯（无重复元素不可复选）

回溯框架：

此题是形式一： 无重复元素不可复选，写回溯算法的时候，for就要从start开始，而不是从0开始！ 即（2,1）和（1,2）是一个结果，故不能复选。
用start来保证每次递归时遍历数组后面未遍历到的数，而不会重复遍历前面的数
最后strat超过数组个数即为终止条件！

注意：
子集问题中，每个节点都是子集 ！
需要在递归的【前序位置】将path添加到res ！而不是到叶子节点才添加到res !
空集 [ ] 也算子集

Java实现：

class Solution {
    
    List<List<Integer>> res=new LinkedList<>();
    LinkedList<Integer> path=new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
    
        if(nums==null){
    
            return new List<List<Integer>>;
        }
        dfs(nums,0);
        return res;
    }

    void dfs(int[] nums,int start){
    
  //用start来保证每次递归时遍历数组后面的数，而不会重复遍历前面的数，
  //最后strat超过数组个数即为终止条件！
  // 空集[]也算子集
        res.add(new LinkedList(path)); // 每个节点都是子集 ！而不是到叶子节点才添加到res !

        for(int i=start;i<nums.length;i++){
    
            //递归前选择
            path.add(nums[i]);
            //递归，i+1确保数组中元素不被重复使用
            dfs(nums,i+1);
            //递归后撤销
            path.removeLast();
        }
    }
}