javascript-代码随想录训练营day24

77.组合

题目链接：

https://leetcode.cn/problems/combinations/

题目描述：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

思路：

​ 本题的要求是求取所有的组合，直观的想法是使用k个for循环嵌套来实现目标。但是这里k的取值是不定的，所以无法直接直接写出所需要的循环。

​ 那么就需要换种思路，使用递归的方法能不能行呢？递归的思想是将问题转化成相同子问题的嵌套，比如摘3个苹果可以变成摘1个苹果+摘1个苹果+摘1个苹果。递归完全可以实现循环的功能。

​ 将本问题拆分如下（n=8,k=3为例）:

写出代码主体：

    let path = [] //存放每一步的组合 
    let res = []  //存放最终结果
    for(let i = 1; i <= n; i++){
        path.push(i) //加入i
        backtracking(i+1) //从i+1,...,n选取k-1个数字，并记录最终结果
        path.pop() //将i清出
    }

backtracking明显为递归的函数，其中需要对终止条件进行设定。终止：path长度等于k即返回。

如果path未满，则在这个子问题中继续上面的拆分过程，选取最初始的数字+从之后的数字中选取m - 1个数字（m为这个子问题中一共要选取的数字个数)

写出该函数：

    function backtracking(start){
        let len = path.length
        //中止条件
        if(len === k){
            res.push([...path])
            return
        }
        //单层逻辑
        for(let j = start; j <= n - (k - len) + 1; j++){ //剪枝操作，个数不足就不用继续循环了
            path.push(j)
            backtracking(j+1)
            path.pop()
        }
    }