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

2023-12-29 18:30:42

力扣(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);
        }
    }
}

文章来源:https://blog.csdn.net/l82049/article/details/135279896
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。