组合问题（回溯法）

1. 组合问题

   
   /**
    给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
   
     示例:
     输入: n = 4, k = 2
     输出:
     [
     [2,4],
     [3,4],
     [2,3],
     [1,2],
     [1,3],
     [1,4],
     ]
    */
   
   function getUnion(n, k) {
   
     let res = []
   
     let path = []
   
     function backtracing(n, k, startIndex) {
   
       if (path.length === 2) { // 终止条件
         res.push([...path]) // 存放结果
         return
       }
   
       for (let i = startIndex; i <= n; i++) {
         path.push(i) // 处理节点
         backtracing(n, k, i + 1) // 递归
         path.pop() // 回溯，撤销处理的节点
       }
     }
   
     backtracing(n, k, 1)
     return res
   
   }
   
   console.log(getUnion(4, 2))
   
   

• 输出结果

  [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]

2. 组合总和（回溯）
   

   var combinationSum3 = function (k, n) {
       // 1. 记录结果集
       const result = [];
       const path = []
   
       const sum = (arr) => arr.reduce((prev, cur) => prev += cur, 0)
   
       // 2. 递归：index -> 索引，sum -> 当前和，path -> 路径
       const recursion = (index, sum) => {
   
           // 2.1 设置递归终止条件：如果它的路径长度等于 k
           if (path.length === k) {
               // 2.1.1 设置收割条件，当它的和为 n 的时候
               if (sum === n) {
                   result.push([...path]); // [...path] : 复制一份新的，避免影响原数组
               }
               // 2.1.2 终止后续递归
               return;
           }
   
           // 2.2 遍历 [index, 9]，从中挑选数字进入 path
           for (let i = index; i <= 9; i++) {
               // 2.2.1 如果 sum + i > n，表明和超标了，没必要下一轮递归
               if (sum + i > n) {
                   break;
               }
   
               // 2.2.2 回溯常用，进进出出的套路
               path.push(i);
               recursion(i + 1, sum + i);
               path.pop();
           }
       };
       recursion(1, 0);
   
       // 3. 返回结果
       return result;
   }
   

   结果：

3. 电话号码的字母组合
   

4. 组合总和
   

5. 分割字符串
   

最后

以上就是顺利饼干为你收集整理的组合问题（回溯法）的全部内容，希望文章能够帮你解决组合问题（回溯法）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。