回溯法(Backtracking)

回溯法(Backtracking)

回溯法本质上是一种，既带有系统性又带有跳跃性的的搜索算法 核心是状态，记录状态，进入状态，状态探索完毕之后，满足或不满足条件都回溯上一个状态。主要操作是递归

它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题.

以77. 组合为例，

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例：

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

这个题目本质上就是求一个组合数，C(n,k) 以题目为例，从四个数里边挑2个，起始状态就是已挑的数为[],未挑选的数为[1,2,3,4],现在进入状态1：挑选数字1，已挑的数为[1],未挑选的数为[2,3,4],不满足条件（挑选两个）继续挑选,进入状态:1-2:继续挑选数字2，已挑的数为[1,2],未挑选的数为[3,4]这时满足状态。记录满足条件的值，并回溯状态，从状态1-2回溯至状态1,已挑的数为[1],未挑选的数为[2,3,4]由于状态1-2已经被挑选过，所以进入状态1-3。
以此类推，进入状态、判断状态是否满足，回溯状态。不断迭代深度优先搜索整个状态树。条件不满足时退出来进行剪枝操作。

引用 & 参考

https://www.cnblogs.com/yuxiaoba/p/8452794.html
https://leetcode-cn.com/problems/combinations/