深度优先搜索算法dfs

深度优先，亦称回溯算法。先沿着某一线路进行搜索，达到条件时返回，切换另一条线路。

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()
    }
}

另外一个关于二叉树搜索的dfs问题