回溯算法经典题目汇总

深碍√TFBOYSˉ_ 2022-09-14 09:12 126阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5reY5reY5piv5Y-q54uX_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

##### 代码模板 #####

let BFS = function (start, target) { 
      let queue = []; // 核心数据结构
      let visited = new Set(); // 避免走回头路
    
      queue.push(start); // 将起点加入队列
      visited.add(start);
      let step = 0; // 记录扩散的步数
    
      while (queue.length !== 0) { 
        let length = queue.length;
        /* 将当前队列中的所有节点向四周扩散 */
        for (let i = 0; i < length; i++) { 
          let cur = queue.shift();
          /* 划重点：这里判断是否到达终点 */
          if (cur === target)
            return step;
          /* 将 cur 的相邻节点加入队列 */
          for (let x = 0; x < n; x++) { 
            if (!visited.has(x)) { 
              queue.push(x);
              visited.add(x);
            }
          }
        }
        /* 划重点：更新步数在这里 */
        step++;
      }
    }

### [77. 组合][77.] ###

var combine = function (n, k) { 
      // 返回的结果集
      let result = []
      // 单层遍历的结果
      let path = []
    
      const backtracking = (n, k, startIndex) => { 
        // 当 path.length === k, 终止
        if (path.length === k) { 
          result.push([...path])
          return
        }
    
        // 单层搜索
        for (let i = startIndex; i <= n; ++i) { 
          // 处理节点
          path.push(i)
          // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
          backtracking(n, k, i + 1)
          path.pop()
        }
      }
    
      // 题目中说，从 1 开始遍历到 n
      backtracking(n, k, 1)
      return result
    };

### [216. 组合总和 III][216. _ III] ###

var combinationSum3 = function (k, n) { 
      let result = []
      let path = []
    
      let backtracking = (n, k, startIndex) => { 
        if (path.length === k && path.reduce((a, b) => a + b) === n) { 
          result.push([...path])
          return
        }
    
        for (let i = startIndex; i <= 9; i++) { 
          path.push(i)
          backtracking(n, k, i + 1)
          path.pop()
        }
      }
    
      backtracking(n, k, 1)
      return result
    };

### [17. 电话号码的字母组合][17.] ###

var letterCombinations = function (digits) { 
      const digitsLength = digits.length;
      // 创建一个结果集
      const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
      if (!digitsLength) return [];
      if (digitsLength === 1) return map[digits].split("");
    
      let result = [];
      let path = [];
    
      const backtracking = (startIndex) => { 
        if (path.length === digitsLength) { 
          result.push(path.join(""));
          return;
        }
        for (const v of map[digits[startIndex]]) { 
          path.push(v);
          backtracking(startIndex + 1);
          path.pop();
        }
      }
    
      backtracking(0);
      return result;
    };

### [39. 组合总和][39.] ###

var combinationSum = function (candidates, target) { 
      let result = [];
      let path = [];
      let startIndex = 0;
      let sum = 0
    
      let backtracking = (sum, startIndex) => { 
        if (sum > target) { 
          return;
        }
        if (sum === target) { 
          result.push([...path])
          return
        }
    
        for (let i = startIndex; i < candidates.length; i++) { 
          sum += candidates[i];
          path.push(candidates[i]);
          backtracking(sum, i);
          sum -= candidates[i];
          path.pop();
        }
      }
    
      backtracking(sum, startIndex)
      return result;
    };

### [40. 组合总和 II][40. _ II] ###

var combinationSum2 = function (candidates, target) { 
      let result = [];
      let path = [];
      let startIndex = 0;
      let sum = 0;
      let used = new Array(candidates.length).fill(false);
      
      candidates.sort();
    
      let backtracking = (sum, startIndex) => { 
        if (sum > target) { 
          return;
        }
        if (sum === target) { 
          result.push([...path])
          return
        }
    
        for (let i = startIndex; i < candidates.length; i++) { 
          if (candidates[i] === candidates[i - 1] && used[i - 1] == false) continue;
          sum += candidates[i];
          path.push(candidates[i]);
          used[i] = true;
          backtracking(sum, i + 1, used);
          used[i] = false;
          sum -= candidates[i];
          path.pop();
        }
      }
    
      backtracking(sum, startIndex)
      return result;
    };

### [131. 分割回文串][131.] ###

var partition = function (s) { 
      let result = [];
      let path = [];
    
      let backtracking = (startIndex) => { 
        if (startIndex === s.length) { 
          result.push([...path])
        }
    
        for (let i = startIndex; i < s.length; i++) { 
          if (isPalindrome(s, startIndex, i)) { 
            let str = s.substr(startIndex, i - startIndex + 1);
            path.push(str);
          } else { 
            continue
          }
          backtracking(i + 1)
          path.pop();
        }
      }
    
      backtracking(0);
      return result;
    };
    
    let isPalindrome = function (s, i, j) { 
      while (i <= j) { 
        if (s[i] !== s[j]) { 
          return false;
        }
        i++;
        j--;
      }
      return true;
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5reY5reY5piv5Y-q54uX_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/df0f29c73d254fe2b245107867516c31.png
[77.]: https://leetcode-cn.com/problems/combinations/
[216. _ III]: https://leetcode-cn.com/problems/combination-sum-iii/
[17.]: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
[39.]: https://leetcode-cn.com/problems/combination-sum/
[40. _ II]: https://leetcode-cn.com/problems/combination-sum-ii/
[131.]: https://leetcode-cn.com/problems/palindrome-partitioning/

发表评论取消回复

表情：

评论列表（有 0 条评论，126人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-回溯算法

一、回溯 1、定义：通过选择不同的岔路口来通往目的地（找到想要的结果）每一步都选择一条路出发，`能进则进，不能进则退回上一步（回溯）`，换一条路再

曾经终败给现在/ 2024年04月08日 09:49/ 0 赞/ 9 阅读

相关回溯算法问题汇总

文章目录模版一. 组合问题 77. 组合 216.组合总和III 17.电话号码的字母组合 39.

深碍√TFBOYSˉ_/ 2024年03月27日 16:38/ 0 赞/ 20 阅读

相关回溯法题目 leetcode

1. [22. 括号生成][22.] 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。示例：输入：n = 3

秒速五厘米/ 2022年12月31日 01:24/ 0 赞/ 90 阅读

相关回溯算法经典题目汇总

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5reY5reY5piv5

深碍√TFBOYSˉ_/ 2022年09月14日 09:12/ 0 赞/ 127 阅读

相关 JavaScript经典题目汇总

变量声明提升 1.考察this指向和变量声明提升 var a = 10; function test(){ a = 100;

我不是女神ヾ/ 2022年07月24日 07:17/ 0 赞/ 118 阅读

相关经典回溯算法之n皇后问题

这是来源于国际象棋的一个问题。n皇后问题要求在一个n×n格的棋盘上放置n个皇后，使得它们彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一条斜线上的

素颜马尾好姑娘i/ 2022年06月07日 00:24/ 0 赞/ 239 阅读

相关 [Leetcode][深度优先/回溯法/DFS]相关题目汇总/分析/总结

题目汇总以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。目前范围：Leetcode前150题深度优先/回溯法题目 [Letter C

心已赠人/ 2022年05月16日 03:54/ 0 赞/ 135 阅读

相关贪心算法题目汇总

贪心算法题目-LeetCode汇总 455.分发饼干 455.分发饼干题目描述 > 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最

水深无声/ 2022年02月03日 12:43/ 0 赞/ 176 阅读

相关 [数据结构][Python][经典题目]Prim算法

from heapq import heappop,heappush def prim(G,s): P,Q = {},[(0,None,s)]

àì夳堔傛蜴生んèń/ 2022年01月23日 04:53/ 0 赞/ 198 阅读

相关 Java实现搜索回溯经典题目

前言搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为

我会带着你远行/ 2021年09月29日 22:44/ 0 赞/ 256 阅读