77. 组合 - 力扣（LeetCode）

回溯法

use::回溯法

解题思路

用另一种思路去画解空间树: 每个数一层, 每个数只有两种选择(两个节点): 取或不取
状态就是两个: 当前搜索到的层数, 以及前面所取得数
对组合而言，无所谓什么最优子结构, 所以操作全局变量来记录搜索到的解

代码

var combine = function(n, k) {
    let rst = []
    function dfs(depth,resolve){//depth就是搜索路径 resolve是状态
        if(resolve.length===k)return rst.push(resolve);//将解记录
        else if(depth===n)return; //剪枝
        dfs(depth+1,[...resolve,depth+1]) //取当前节点
        dfs(depth+1,resolve) //不取当前节点
    }
    dfs(0,[])
    return rst
};