代码随想录补|leetcode78 子集问题

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

这道题和之前的组合问题不一样的是，组合问题是获得叶子节点的结果，这个子集问题是每一次的遍历都是结果。回溯图如图所示：

?所以result.add()这个操作应该放在回溯函数的开头，这样也可以很巧妙的把[ ]这个空集合add进去。

这道题回溯结束的条件是startIndex == nums.length(),因为这代表已经把这个数组遍历了一遍。同组合问题，为了防止（1，2），（2，1）这种重复子集出现，每次回溯时startIndex++。

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