39. Combination Sum（js）

39. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
题意：找出数组中所有排列组合使得其和等于target
代码如下：

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
//回溯算法
var combinationSum = function(candidates, target) {
        let res=[];
        let list=[];
        candidates.sort((a,b)=>a-b);
        backTrack(res,list,candidates,target,0);
        return res;
}
var backTrack=function(res,list,candidates,target,start){
        if(target>0){
            for(let i=start;i<candidates.length && target>=candidates[i];i++){
                list.push(candidates[i]);
                backTrack(res,list,candidates,target-candidates[i],i);
                list.pop();
            }
        }else if(target==0){
            res.push([...list]);
        }
}