4.组合总数

• 1.12
  • 这里也要控住不回头

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer>path= new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates,target,0,0);
        return res;
    }
    public void backtrack(int[] candidates,int target,int count,int start){
        if(count==target){
            res.add(new ArrayList<>(path));
            return;
        }
        if(count>target) return;
        for(int i=start;i<candidates.length;i++){
            path.add(candidates[i]);
            backtrack(candidates,target,count+candidates[i],i);
            path.remove(path.size()-1);
        }
    }
}

• 2.3
  • 想难了，回溯的特性就是会重复遍历每一种情况，所以在回溯参数中加入 sum 参数和 start 参数（控制不回头，以去重【2,3】和【3,2】这种重复情况）
• 11.21
  • 回溯函数需要有一个sum参数和start参数
  • 感觉比前三个简单

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates,target,0,0);
        return res;
    }
    public void backtrack(int[] nums,int target,int sum,int start){
        if(sum==target){
            res.add(new ArrayList<>(path));
            return;
        }
        if(sum>target) return;
        for(int i=start; i<nums.length;i++){
            path.add(nums[i]);
            backtrack(nums,target,sum+nums[i],i);//i,不是i+1,可以被重复使用
            path.remove(path.size()-1);
        }
    }
}

• 这里要注意加一个开始标记和总和标记
• 退出条件为相等
• 注意sum>target时进行剪枝
• 可以被重复使用
• test