# 回溯

回溯算法（Backtracking）也叫试探法，是一种能避免不必要搜索的穷举式的搜索算法。

基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。 满足回溯条件的某个状态的点称为“回溯点”。

回溯比暴力穷举法更高明的地方就是回溯算法使用剪枝函数，剪去一些不可能到达 最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。

回溯的特点：

* 深度优先遍历。
* 求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。
* 求任一解时，只要搜索到问题的一个解就可以结束。

## 一般步骤

1. 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
2. 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
3. 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

```js
const result = []; // 存放所欲符合条件结果的集合
const curPath = []; // 存放当前符合条件的结果

const backtracking = (eleList, curPath = [], result = []) => {
  if (遇到边界条件) {
    result.push(curPath);
  } else {
    // 枚举可选元素列表
    for (let ele of eleList) {
      curPath.push(ele);
      backtracking(eleList, curPath, result);
      path.pop(); // 回溯
    }
  }
};

// backtracking(eleList)
```

## 剪枝

某些问题如果其解空间过大，即使用回溯法进行计算也有很高的时间复杂度，因为回溯法会尝试解空间树中所有的分支。

优化剪枝策略，就是判断当前的分支树是否符合问题的条件，如果当前分支树不符合条件，那么就不再遍历这个分支里的所有路径。

启发式搜索策略指的是，给回溯法搜索子节点的顺序设定一个优先级，从该子节点往下遍历更有可能找到问题的解。

## 使用场景

### 排列组合

[Leetcode 77: Combinations](https://leetcode.com/problems/combinations/description/)

给定两个整数 n 和 k，返回范围 \[1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。

```js
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
  const result = [];

  const dfs = (curPath = []) => {
    const curPathLen = curPath.length;
    if (curPathLen === k) {
      result.push(curPath.slice());
    } else {
      const peek = curPath[curPathLen - 1] || 0;
      for (let ele = peek + 1; ele <= n; ++ele) {
        curPath.push(ele);
        dfs(curPath);
        curPath.pop();
      }
    }

    return result;
  };

  dfs();

  return result;
};
```

### 分割回文串

[Leetcode 131](https://leetcode.com/problems/palindrome-partitioning/description/)

“给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。”

```js
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  const palindromeStrCache = new Map();
  const isPalindromeStr = (str, start, end) => {
    const key = `${start},${end}`;
    if (palindromeStrCache.has(key)) {
      return palindromeStrCache.get(key);
    }

    if (start >= end) {
      palindromeStrCache.set(key, true);
    } else if (str[start] === str[end]) {
      // 基于 DP 的计算是否是 Palindrome
      palindromeStrCache.set(key, isPalindromeStr(str, start + 1, end - 1));
    } else {
      palindromeStrCache.set(key, false);
    }

    return palindromeStrCache.get(key);
  };

  const dfs = (startIndex, curPath, result) => {
    const strLen = s.length;
    if (startIndex < strLen) {
      for (let endIndex = startIndex; endIndex < strLen; ++endIndex) {
        if (isPalindromeStr(s, startIndex, endIndex)) {
          curPath.push(s.slice(startIndex, endIndex + 1));
          // 执行具体的逻辑
          dfs(endIndex + 1, curPath, result);
          // 回溯
          curPath.pop();
        }
      }
    } else {
      // 达到终点，加入最终结果
      result.push(curPath.slice());
    }

    return result;
  };

  return dfs(0, [], []);
};
```

## 参考

[五大基本算法之回溯算法 backtracking](https://houbb.github.io/2020/01/23/data-struct-learn-07-base-backtracking) [回溯算法知识](https://algo.itcharge.cn/09.Algorithm-Base/04.Backtracking-Algorithm/01.Backtracking-Algorithm/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://xyy94813.gitbook.io/x-note/ji-chu-suan-fa/backtracking.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.