LeetCode：39. Combined sum

To give you one No repeating elements Array of integers for candidates And a target integer target , find candidates You can make the sum of numbers as the target number target Of all Different combinations , And return... As a list . You can press In any order Return these combinations .

candidates Medium The same Numbers can Unlimited repeat selected . If the selected number of at least one number is different , Then the two combinations are different .

For a given input , Guarantee and for target The number of different combinations of is less than 150 individual .

Example 1：

 Input ：candidates = [2,3,6,7], target = 7
 Output ：[[2,2,3],[7]]
 explain ：
2  and  3  Can form a set of candidates ,2 + 2 + 3 = 7 . Be careful  2  You can use it multiple times .
7  Is also a candidate , 7 = 7 .
 Only these 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 : []

Tips ：

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidate Every element in is Different from each other
• 1 <= target <= 500

---

Their thinking

1. Using backtracking （ namely DFS Prune with constraints ）： First, ascending the array , Then define recursive functions , But pay attention to ： Numbers can be reused , So every recursion , The starting point of incoming is i
2. Use two conditions to prune , Recursive exit ：

• Meet the conditions , Copy one into the result array
• The number of remaining targets is less than the current element , The latter elements will only be larger , Abandon this round directly

Backtracking and DFS, The main difference is , The backtracking method does not retain the complete tree structure in the solution process , While depth first search records the complete search tree

Code

/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */
var combinationSum = function(candidates, target) {
    
    const res = [];
    //  Ascending sort 
    candidates.sort((a, b) => a - b);
    const search = (path, target, start) => {
    
        if (target === 0) {
    
            //  Meet the conditions , Copy one into the result array 
            res.push([...path]);
            return;
        }
        //  Note that the starting point is start
        for (let i = start; i < candidates.length; i++) {
    
            //  The number of remaining targets is less than the current element , The latter elements will only be larger , Abandon this round directly 
            if (target < candidates[i]) return;
            path.push(candidates[i]);
            //  Numbers can be repeated , So the introduction i
            search(path, target - candidates[i], i);
            path.pop();
        }
    };
    search([], target, 0);
    return res;
};