1. Toy模板网首页
  2. > Toy博客

【算法】回溯算法

9月前 作者：codecapture 分类：Toy博客 阅读(27) 违法举报

这篇具有很好参考价值的文章主要介绍了【算法】回溯算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本文参考《代码随想录》
原文笔记链接：
https://www.programmercarl.com/
B站视频链接：
https://www.bilibili.com/video/BV1cy4y167mM?spm_id_from=333.337.search-card.all.click&vd_source=c2d3149b8b6fdae1d68e10dfaabfb1de

回溯算法理论基础

题目分类大纲如下：

回溯算法,算法,算法,leetcode

回溯算法概述

回溯法简单来说就是按照深度优先的顺序，穷举所有可能性的算法，但是回溯算法比暴力穷举法更高明的地方就是回溯算法可以随时判断当前状态是否符合问题的条件。一旦不符合条件，那么就退回到上一个状态，省去了继续往下探索的时间。
回溯是递归的副产品，只要有递归就会有回溯。

回溯法的效率

虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？
因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等

注意：
组合是不强调元素顺序的，排列是强调元素顺序。
例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构，所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度都构成的树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

回溯法模板

  • 回溯函数模板返回值以及参数
    回溯算法中函数返回值一般为void。关于参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
    回溯函数伪代码如下：
void backtracking(参数)
  • 回溯函数终止条件
    什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
    所以回溯函数终止条件伪代码如下：
if (终止条件) {
    存放结果;
    return;
}

回溯搜索的遍历过程
回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
如图：
回溯算法,算法,算法,leetcode
注意图中，我特意举例集合大小和孩子的数量是相等的！

回溯函数遍历过程伪代码如下：

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
分析完过程，回溯算法模板框架如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

回溯算法例题一——组合问题

题目：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
leetcode链接：https://leetcode.cn/problems/combinations/

示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2：
输入：n = 1, k = 1
输出：[[1]]

思路

本题这是回溯法的经典题目。
直接的解法当然是使用for循环，例如示例中k为2，很容易想到 用两个for循环，这样就可以输出 和示例中一样的结果。
代码如下：

int n = 4;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        cout << i << " " << j << endl;
    }
}

输入：n = 100, k = 3 那么就三层for循环，代码如下：

int n = 100;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        for (int u = j + 1; u <= n; n++) {
            cout << i << " " << j << " " << u << endl;
        }
    }
}

但当k很大的情况下，譬如k=50，暴力写法需要嵌套50层for循环，会让人感到绝望。那么我们可以使用回溯法就用递归来解决嵌套层数的问题。
递归来做层叠嵌套（可以理解是开k层for循环），**每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。**此时递归的层数大家应该知道了，例如：n为100，k为50的情况下，就是递归50层。
上面说到回溯法解决的问题都可以抽象为树形结构（N叉树），用树形结构来理解回溯就容易多了。将组合问题抽象成树形结构如下：
回溯算法,算法,算法,leetcode
可以看出这个棵树，一开始集合是 1，2，3，4， 从左向右取数，取过的数，不在重复取。
第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
图中可以发现n相当于树的宽度，k相当于树的深度。

图中每次搜索到了叶子节点，我们就找到了一个结果,只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。

回溯三部曲

  • 递归函数的返回值以及参数
    在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
    代码如下：
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();

其实不定义这两个全局遍历也是可以的，把这两个变量放进递归函数的参数里，但函数里参数太多影响可读性，所以我定义全局变量了。
函数里一定有两个参数，既然是集合n里面取k的数，那么n和k是两个int型的参数。

然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,…,n] ）。
为什么要有这个startIndex呢？
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex。
从下图中红线部分可以看出，在集合[1,2,3,4]取1之后，下一层递归，就要在[2,3,4]中取数了，那么下一层递归如何知道从[2,3,4]中取数呢，靠的就是startIndex。
回溯算法,算法,算法,leetcode
所以需要startIndex来记录下一层递归，搜索的起始位置。
所以这一部分代码为：

List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
private void backtracking(int n, int k, int startIndex)
  • 回溯函数终止条件
    什么时候到达所谓的叶子节点了呢？
    path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。
    如图红色部分：
    回溯算法,算法,算法,leetcode
    此时用result二维数组，把path保存起来，并终止本层递归。
    所以终止条件代码如下：
if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
  • 单层搜索的过程
    回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。
    回溯算法,算法,算法,leetcode
    如此我们才遍历完图中的这棵树。
    for循环每次从startIndex开始遍历，然后用path保存取到的节点i。
    代码如下：
        for (int i = startIndex; i <= n; i++) {
            path.push(i); // 处理节点 
            backtracking(n, k, i + 1); // 递归
            path.pop(); // 回溯，撤销处理的节点
        }

可以看出backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。
backtracking的下面部分就是回溯的操作了，撤销本次处理的结果。
完整代码如下：

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    /**
     * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
     * @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
     */
    private void backtracking(int n, int k, int startIndex){
        //终止条件
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n; i++){
            path.push(i);
            backtracking(n, k, i + 1);
            path.pop();
        }
    }
}

组合问题剪枝优化

回溯法虽然是暴力搜索，但也有时候可以有点剪枝优化一下的。
在遍历过程中：

for (int i = startIndex; i <= n; i++) {
    path.push(i);
    backtracking(n, k, i + 1);
    path.pop();
}

如何优化呢？我们可以从这个循环下手。
举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。在第二层for循环，从元素3开始的遍历都没有意义了。如图所示：
回溯算法,算法,算法,leetcode
图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。所以如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
优化过程如下：

  1. 已经选择的元素个数：path.size();
  2. 还需要的元素个数为: k - path.size();
  3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历。
    关于+1的问题：
    因为包括起始位置，我们要是一个左闭的集合。
    举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。从2开始搜索都是合理的，可以是组合[2, 3, 4]。
    所以优化之后的for循环为：
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

优化后的整体代码：

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    /**
     * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
     * @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
     */
    private void backtracking(int n, int k, int startIndex){
        //终止条件
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
            path.push(i);
            backtracking(n, k, i + 1);
            path.pop();
        }
    }
}

回溯算法例题二——组合总和问题

题目：给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个

链接：https://leetcode.cn/problems/combination-sum

示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：
输入: candidates = [2], target = 1
输出: []

提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都 互不相同
1 <= target <= 500

思路

相对于上一题组合问题，本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。
本题搜索的过程抽象成树形结构如下：
回溯算法,算法,算法,leetcode
注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！

回溯三部曲

递归函数参数
定义两个全局变量：

List<List<Integer>> lists=new ArrayList<>();//存放结果集
LinkedList<Integer> list=new LinkedList();//存放符合条件的结果

首先是题目中给出的参数，集合candidates, 和目标值target。此外还定义了int型的sum变量来统计单一结果path里的总和。本题还需要startIndex来控制for循环的起始位置
代码如下：

 public void backtracing(int[] candidates, int target,int sum,int startIndex)

递归终止条件
如下图树形结构中，从叶子节点可以清晰看到，终止只有两种情况，sum大于target和sum等于target，且当sum等于target需要收集结果。
回溯算法,算法,算法,leetcode
代码如下：

 if (sum==target)
        {
            lists.add(new LinkedList<>(list));
            return;
        }
        if (sum>target)
        {
            return;
        }

单层搜索的逻辑
单层for循环依然是从startIndex开始，搜索candidates集合。与上一题的区别在于本题元素可重复。

for (int i=startIndex;i<candidates.length;i++){
              list.add(candidates[i]);
            sum=sum+candidates[i];
            backtracing(candidates,target,sum,i);//关键点：使用i，表示可以直接重复读取当前元素
            sum=sum-candidates[i];//回溯
            list.removeLast();//回溯
        }

完整代码如下：

class Solution {
    List<List<Integer>> lists=new ArrayList<>();
    LinkedList<Integer> list=new LinkedList();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int sum=0;
        backtracing(candidates,target,sum,0);
        return lists;
    }
    public void backtracing(int[] candidates, int target,int sum,int startIndex){
        if (sum==target)
        {
            lists.add(new LinkedList<>(list));
            return;
        }
        if (sum>target)
        {
            return;
        }
        for (int i=startIndex;i<candidates.length;i++){
              list.add(candidates[i]);
            sum=sum+candidates[i];
            backtracing(candidates,target,sum,i);
            sum=sum-candidates[i];
            list.removeLast();
        }
    }
}

剪枝优化

回溯算法,算法,算法,leetcode
在如上图的树形结构之中，对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。
对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。
如图：
回溯算法,算法,算法,leetcode
for循环剪枝代码如下：

for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)

优化后代码如下：

class Solution {
    List<List<Integer>> lists=new ArrayList<>();//存放结果集
    LinkedList<Integer> list=new LinkedList();//存放符合条件的结果
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int sum=0;
        Array.sort(candidates);// 需要排序
        backtracing(candidates,target,sum,0);
        return lists;
    }
    public void backtracing(int[] candidates, int target,int sum,int startIndex){
        if (sum==target)
        {
            lists.add(new LinkedList<>(list));
            return;
        }
        if (sum>target)
        {
            return;
        }
        // 如果 sum + candidates[i] > target 就终止遍历
        for (int i=startIndex; i < candidates.length && sum + candidates[i] <= target;i++){
            list.add(candidates[i]);
            sum=sum+candidates[i];
            backtracing(candidates,target,sum,i);
            sum=sum-candidates[i];
            list.removeLast();
        }
    }
}

回溯算法例题三——分割回文串

题目：给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”]
力扣链接：https://leetcode.cn/problems/palindrome-partitioning/

示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：
输入：s = “a”
输出：[[“a”]]

提示：
1 <= s.length <= 16
s 仅由小写英文字母组成

思路

本题这涉及到两个关键问题：
1、切割问题，有不同的切割方式
2、判断回文

这种题目，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯。
一些同学可能想不清楚 回溯究竟是如何切割字符串呢？我们来分析一下切割，其实切割问题类似组合问题。

例如对于字符串abcdef：

  • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…。
  • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…。
    所以切割问题，也可以抽象为一棵树形结构，如图：回溯算法,算法,算法,leetcode
    递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
    此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

回溯三部曲

  • 递归函数参数
    全局变量path存放切割后回文的子串，result存放结果集。 （这两个参数可以放到函数参数里）
    本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。
    代码如下：
 LinkedList<String> path=new LinkedList<>();
 List<List<String>> result=new ArrayList<>();`
  • 递归函数终止条件
    回溯算法,算法,算法,leetcode
    从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止终止条件。
    那么在代码里什么是切割线呢？
    在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。
    所以终止条件代码如下：
public void  backtracking(String s,int startIndex){
        if (startIndex>=s.length()){
            result.add(new LinkedList<>(path));
            return;
        }
  }

来看看在递归循环，中如何截取子串呢？

在for (int i = startIndex; i < s.size(); i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文，如果是回文，就加入在path中，path用来记录切割过的回文子串。

 for (int i=startIndex;i<s.length();i++){
            if (isPlalindrome(s.substring(startIndex,i+1))){
                path.add(s.substring(startIndex,i+1));
                backtracking(s,i+1);
                path.removeLast();
            }else {
                continue;
            }
        }

注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1。
完整代码如下：

class Solution {
      LinkedList<String> path=new LinkedList<>();
    List<List<String>> result=new ArrayList<>();
    public List<List<String>> partition(String s) {
        backtracking(s,0);
        return result;
    }
    
    //回文判断，详见算法专栏《判断回文字符串》
    public boolean isPlalindrome(String s){
        StringBuilder sb=new StringBuilder(s);
        sb.reverse();
        return sb.toString().equals(s);
    }
    
    public void  backtracking(String s,int startIndex){
        if (startIndex>=s.length()){
            result.add(new LinkedList<>(path));
            return;
        }
        for (int i=startIndex;i<s.length();i++){
            if (isPlalindrome(s.substring(startIndex,i+1))){
                path.add(s.substring(startIndex,i+1));
                backtracking(s,i+1);
                path.removeLast();
            }else {
                continue;
            }
        }
    }
}

结果：
回溯算法,算法,算法,leetcode文章来源地址https://www.toymoban.com/news/detail-566603.html

到了这里，关于【算法】回溯算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • leetcode473. 火柴拼正方形（回溯算法-java）

    leetcode473. 火柴拼正方形（回溯算法-java）

    难度 - 中等 原题链接 - leetcode473 火柴拼正方形 你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。 如果你能使这个正

    2024年02月12日
    浏览(42)
  • leetCode 131.分割回文串 + 动态规划 + 回溯算法 + 优化 + 图解 + 笔记

    leetCode 131.分割回文串 + 动态规划 + 回溯算法 + 优化 + 图解 + 笔记

    我的往期文章： leetCode 647.回文子串 动态规划 + 优化空间 / 中心扩展法 + 双指针-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/133883091?spm=1001.2014.3001.5501 leetCode 131.分割回文串 + 回溯算法 + 图解 + 笔记-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/134700907?spm=1001.2014.3001

    2024年02月05日
    浏览(53)

  • 【leetcode刷题之路】剑指Offer（3）——搜索与回溯算法

    7 搜索与回溯算法 7.1 【BFS】剑指 Offer 32 - I - 从上到下打印二叉树 https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/   这里借助队列来实现广度优先遍历，由于需要访问每一层的节点，而且这一层访问才可以访问下一层，所以可以考虑队列的先进先出，先把每一层的节

    2024年02月13日
    浏览(56)
  • 代码随想录Day20 回溯算法 LeetCode77 组合问题

    代码随想录Day20 回溯算法 LeetCode77 组合问题

    以下内容更详细解释来自于:代码随想录 (programmercarl.com) 回溯法也叫回溯搜索法,是搜索法的一种,我们之前在二叉树中也经常使用到回溯来解决问题,其实 有递归就有回溯 ,有的时候回溯隐藏在递归之下,我们不容易发觉,今天我们来详细介绍一下什么是回溯,它能解决哪些问题.

    2024年02月08日
    浏览(52)
  • 算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习一（leetcode真题剖析）

    算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习一（leetcode真题剖析）

    题目链接：https://leetcode.cn/problems/permutations/ 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1： 示例 2： 示例 3： 提示： 1 = nums.length = 6 -10 = nums[i] = 10 nums 中的所有整数 互不相同 思路 这是一个典型的回溯问题，需要在每

    2024年02月21日
    浏览(64)

  • LeetCode算法题解（回溯）|39. 组合总和、40. 组合总和 II、131. 分割回文串

    题目链接：39. 组合总和 题目描述： 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ，找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ，并以列表形式返回。你可以按  任意顺序  返回这些组合。 candidates  中的  同一个  数

    2024年02月05日
    浏览(59)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷：全排列、组合、子集

    【数据结构】回溯算法公式化解题 leetcode经典题目带刷：全排列、组合、子集

    一、什么是回溯算法 回溯算法（Backtracking Algorithm）是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解，当发现当前选择不符合要求时，就回溯到之前的状态，然后尝试其他的选择。 1、基本思想： 从问题的起

    2024年02月11日
    浏览(42)
  • 【Leetcode60天带刷】day27回溯算法——39. 组合总和，40.组合总和II，131.分割回文串

    【Leetcode60天带刷】day27回溯算法——39. 组合总和，40.组合总和II，131.分割回文串

    ​ 39. 组合总和 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ，找出  candidates  中可以使数字和为目标数  target  的 所有   不同组合  ，并以列表形式返回。你可以按  任意顺序  返回这些组合。 candidates  中的  同一个  数字可以  无限制重复

    2024年02月11日
    浏览(45)
  • 【Leetcode60天带刷】day33回溯算法——1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果

    【Leetcode60天带刷】day33回溯算法——1005.K次取反后最大化的数组和 134. 加油站 135. 分发糖果

    ​ 1005. K 次取反后最大化的数组和 给你一个整数数组  nums  和一个整数  k  ，按以下方法修改该数组： 选择某个下标  i  并将  nums[i]  替换为  -nums[i]  。 重复这个过程恰好  k  次。可以多次选择同一个下标  i  。 以这种方式修改数组后，返回数组  可能的最大和  。

    2024年02月11日
    浏览(39)

  • LeetCode——回溯篇（二）

    刷题顺序及思路来源于代码随想录，网站地址：https://programmercarl.com 目录 131. 分割回文串 93. 复原 IP 地址 78. 子集 90. 子集 II 491. 递增子序列 给你一个字符串  s ，请你将   s   分割成一些子串，使每个子串都是  回文串  。返回  s  所有可能的分割方案。 回文串  是正

    2024年02月11日
    浏览(26)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包