深度优先，亦称回溯算法。先沿着某一线路进行搜索，达到条件时返回，切换另一条线路。
treeSearch.jpg
该算法可以涵盖所有情况，对于搜索比较适合。
如数组，tree搜索
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Note:
All numbers will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]
//javascript
var combinationSum3 = function(k, n) {
let res=[]
let temp=[]
if(k===0) return [];
if(n/k>9)return [];
dfs(res,temp,n,k,1)
return res
};
function dfs(res,temp,remain,num,cur){
if(remain<0) return
//当达到k的阈值
if(num===0){
if(remain===0){
let tmp=temp.slice(0,temp.length);//数组拷贝
res.push(tmp)
}
return
}
for(let i=cur;i<=9;i++){
temp[temp.length]=i;
//搜索下一个值
dfs(res,temp,remain-i,num-1,i+1);
temp.pop()
}
}
