Leetcode-78. 子集

78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

输入：nums = [0]
输出：[[],[0]]
解题思路
还是利用回溯算法框架
结束条件是每一个路径都可以作为结果存入
为了避免重复，每次记录当前索引，不往前遍历。只遍历之后的元素
也就是【1,2,3】，先选1，再就只能在2,3里选。如果先选2，则只能选3，不能选1

class Solution {
    List<List<Integer>> res=new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        LinkedList<Integer> track=new LinkedList<>();
        backtrack(nums,0,track);
        return res;

    }
    //从start索引开始遍历元素
    public void backtrack(int[] nums,int start,LinkedList<Integer> track){
        //子集-每个中间结果都保留
        res.add(new LinkedList(track));
        //每次只遍历后边的
        for(int i=start;i<nums.length;i++){
            track.add(nums[i]);
            backtrack(nums,i+1,track);
            track.removeLast();
        }
    }
}