Day 24 | 回溯算法理论基础、77.组合

回溯算法理论基础

讲解：https://www.bilibili.com/video/BV1cy4y167mM

什么是回溯法

• 回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
• 回溯是递归的副产品，只要有递归就会有回溯。
• 回溯函数也就是递归函数，指的都是一个函数。

• 因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

  回溯法解决的问题

• 组合问题：N个数里面按一定规则找出k个数的集合

• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

• 注意：组合是不强调元素顺序的，排列是强调元素顺序。

  如何理解回溯法

• 回溯法解决的问题都可以抽象为树形结构（N叉树）

• 因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。
• for循环横向遍历，递归纵向收集path。
  

Leetcode 77.组合

题目：77.组合 讲解：https://www.bilibili.com/video/BV1ti4y1L7cv 剪枝：https://www.bilibili.com/video/BV1wi4y157er

初始思路

如果k很大的话，双层for循环是解决不了的，k为几就要套几层for循环。

代码

var combine = function (n, k) {
    let result = []
    let path = []
    const backtracking = (n, k, startIndex) => {
          // 当临时路径中元素有k个元素的时候，说明已经取到想要的组合了
        if (path.length === k) {
            result.push([...path])
            return
        }
          // startIndex说明从哪个元素开始，前面的几个元素就不取了
        for (let i = startIndex; i <= n; i++){
            path.push(i)
            backtracking(n, k, i + 1)
            path.pop()
        }
    }
    backtracking(n, k, 1)
    return result
};

var combine = function (n, k) {
    let result = []
    let path = []
    const backtracking = (n, k, startIndex) => {
        if (path.length === k) {
            result.push([...path])
            return
        }
        for (let i = startIndex; i <= n - (k - path.length) + 1; i++){
            path.push(i)
            backtracking(n, k, i + 1)
            path.pop()
        }
    }
    backtracking(n, k, 1)
    return result
};

感想

1. 图示
   
2. 剪枝操作：如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。