LeetCode 39：组合总和

小半 • 2023年2月3日上午10:52 • 技术随笔 • 阅读 276

题目：

回溯：子集/组合（元素无重可复选）有序用start

组合总和问题还是属于组合问题，只是再增加一个sum变量！
由于可重复选， if(sum>target){ return; } 否则栈溢出！

组合问题和子集问题等价；
之前的组合/子集问题中，通过这个 i 从 start 开始，那么下⼀层回溯树就是从 start + 1 开始，从⽽保证 nums[start] 这个元素不会被重复使⽤：
那么反过来，如果想让每个元素被重复使⽤，我只要把 i + 1 改成 i 即可！

这相当于给之前的回溯树添加了⼀条树枝，在遍历这棵树的过程中，⼀个元素可以被⽆限次使⽤：

需要设置合适的终止条件以结束算法，即路径和⼤于 target 时就没必要再遍历下去了。

总结：
元素无重不可复选：
组合/子集通过传入参数start来保证不重复使用元素
排列使用onPath或者path.contains来保证不重复使用元素

元素可重不可复选：
组合/子集通过 i>start && nums[i]==nums[i-1] 来限制；
排列通过i>0 && nums[i]==nums[i-1] && !onPath[i-1]来限制；

元素无重可复选：
组合/子集还是用start来遍历，递归时将strat+1改为start以重复使用；
排列则去掉onPath或者path.contains即可。

Java实现：

class Solution {
    int sum=0;
    List<List<Integer>> res=new LinkedList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] nums, int target) {
        //无重复不需要排序
        dfs(nums,target,0);
        return res;
    }

    void dfs(int[] nums,int target,int start){
        if(sum>target){ //=终止条件1
            return;
        }
        if(sum==target){ //=终止条件2
            res.add(new LinkedList(path));
        }
        for(int i=start;i<nums.length;i++){
            //选择
            sum+=nums[i];
            path.add(nums[i]);
            //
            dfs(nums,target,i);
            //撤销
            sum-=nums[i];
            path.removeLast();
        }
    }
}