回溯法

回溯法是一种试探性的算法。它建立在递归的基础上，在不满足条件的情况下，立刻停止前进，返回之前的状态。

基本算法结构

def fn(n, solution):
    # 1. 判断输入是否非法
    if n < 0:
        return

    # 2. 判断递归是否要结束
    if n == len(solution):
        return True

    # 3. 遍历所有可能的情况
    for i in range(n):
        solution.append(i)
        # 递归
        fn(i, solution)
        # 4. 回退到上一步骤
        solution.pop()

例如N皇后问题

在一个 nxn 的国际棋盘上放置皇后，保证每行每列，每个斜对角方向只有一个皇后，求解所有可能的解法。

假设我们是一个 4x4 的棋盘，使用暴力解法先枚举出来 4⁴ 种可能的组合方式，然后依次判断每一种是否可用。这种算法的时间复杂度相当于 O(nⁿ)

先给出如何判定是否合法的函数:

# data 里面保存的是每一行有皇后的列索引
def valid(data):
    row = len(data) - 1
    r = data[row]
    for i in range(row):
        # 检测垂直和斜对角方向是否有其它棋子
        if data[i] == r or (abs(data[i] - r) == (row - i)):
            return False
    return True

使用回溯法解决这个问题的代码：

def backtracking(n, data, results):
    row_num = len(data)
    # 摆放完成的情况
    if row_num == n:
        results.append(data.copy())
        return
    for col in range(n):
        data.append(col)
        # 检查是否符合要求。满足的时候执行递归
        if valid(data):
            backtracking(n, data, results)
        # 恢复之前的状态继续尝试
        data.pop()


def nquene(n, results):
    data = []
    backtracking(n, data, results)

时间复杂度进行分析

观察 backtracking 函数，其中有一个长度为 n 的遍历，然后算法核心部分是递归和valid 判定
所以算法的整体负载度为：T(n) = n * (T(迭代) + T(valid))

• valid 函数的时间复杂度是随 data 的长度而增长的，最大的情况下为 O(n)
• 迭代部分每次将问题的规模缩小1

所以T(n) = n * (T(n - 1) + O(n)) = n * T(n - 1) + O(n²)
这个样式不满足公式法的模板，所以我们使用迭代法进行分析

T(n) = n*((n - 1) * T(n - 2) + O(n-1)^2) + O(n^2)
T(n) = (n * (n - 1) * (n - 2) ... * 1) + (1 + 2^2 + 3^2 + ... + n^2)

前面是 n 的阶乘，后面是n 的平方和。利用平方和公式可以得知
T(n) = n! + O(n * (n + 1) * (2n + 1) / 6)
化简得到: T(n) = n! + O(n^3)
因为阶乘的变化趋势要大于立方，所以最终时间复杂度为 T(n) = n!