DataStructure_Algorithm_HandBook_PreForLeetCode

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the

frequency

of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

solution

这道题目和上一题不一样的点在于是可以重复选择数字，只要其中一个数字出现的次数不一样，就算是不同的组合。

由于每个元素是重复选的，我们的 index 就不需要加 1 了

但是没有必要回去考虑，因为在 i 的位置的所有情况都考虑到了，下一次就是从 i 开始往后考虑就可以了

这个很像完全背包的问题

什么时候终止呢？ 和大于等于 target 就终止了

var combinationSum = function(candidates, target) {
    let result =[];
    dfs(0,[],0,candidates,target,result);
    return result;
}; 

function dfs(index,path,sum,candidates,target,result){
    if(sum > target){
        return; 
    }
    if(sum === target){
        result.push([...path]);
        return; 
    }
    for(let i = index;i < candidates.length;i++){
        path.push(candidates[i]);
        dfs(i, path, sum + candidates[i], candidates, target, result);
        path.pop(); // 回溯，移除最后一个数字，尝试其他可能的组合
    }
}

我们可以做个剪枝优化

var combinationSum = function(candidates, target) {
    let result =[]; 
    candidates.sort((a,b)=>a-b);
    dfs(0,[],0,candidates,target,result);
    return result;
}; 

function dfs(index,path,sum,candidates,target,result){
    if(sum > target){
        return; 
    }
    if(sum === target){
        result.push([...path]);
        return; 
    }
    for(let i = index;i < candidates.length;i++){
        //剪枝
        //如果说此时的 sum+candidates【i】已经超过 target，就直接 return
        //前提是我们的数组是有序的 
        if(candidates[i]+sum > target) return; 
        path.push(candidates[i]);
        dfs(i, path, sum + candidates[i], candidates, target, result);
        path.pop(); // 回溯，移除最后一个数字，尝试其他可能的组合
    }
}