解决哪类问题

:::success 找到所有可能路径 :::

代码模板

  • 模板要素
    • 路径集<路径<选择>>的含义？
    • 结束条件是什么？
    • 如何枚举选择？
    • 选择如何符合要求？
      1. List<List<Integer>> 路径集 = new ArrayList<>();
      2. private void backtrack(路径, 选择or选择列表) {
      3. if(满足结束条件) {
      4.    路径集.add(路径); // 深拷贝
      5.    return;
      6. }
      7. for (选择: 选择列表) {
      8.    if(选择符合要求) {
      9.        路径.add(选择); // 做选择
      10.        backtrack(路径, 新选择or新选择列表); // 对新的未探索区域递归
      11.        路径.remove(路径.size() - 1); // 撤销选择
      12.    }
      13. }
      14. }

      复杂度

      O(所有节点的规模)

      运用思想

      回溯、递归

      例题

      | 题目 | 难度 | 推荐指数 | | —- | —- | —- | | 17. 电话号码的字母组合 | 中等 | 🤩🤩🤩🤩 | | 37. 解数独 | 困难 | 🤩🤩🤩🤩 | | 39. 组合总和 | 中等 | 🤩🤩🤩🤩 | | 40. 组合总和 II | 中等 | 🤩🤩🤩🤩 | | 90. 子集 II | 中等 | 🤩🤩🤩🤩 | | 131. 分割回文串 | 中等 | 🤩🤩🤩🤩 | | 212. 单词搜索 II | 困难 | 🤩🤩🤩 | | 301. 删除无效的括号 | 困难 | 🤩🤩🤩🤩 | | 306. 累加数 | 中等 | 🤩🤩🤩🤩 | | 797. 所有可能的路径 | 中等 | 🤩🤩🤩🤩 | | 1219. 黄金矿工 | 中等 | 🤩🤩🤩🤩🤩 | | 剑指 Offer 38. 字符串的排列 | 中等 | 🤩🤩🤩🤩 |