【进击的算法】基础算法——回溯算法

java8

帖子摘要：本节主题回溯算法 更多算法深入聊聊KMP算法 我的主页蓝色学者的个人主页   文章目录 一、前言二、概念三、例题1.题目全排列2.解题思路回溯算法的本质问题1问题2问题3        3.总结4.参......

( E& c0 R1 R" @. e5 s$ m9 a0 r& j大家好，欢迎来到Java吧（www.java8.com），交流、学习Java技术、获取Java资源无任何套路，今天说一说：“【进击的算法】基础算法——回溯算法”
3 `$ g, Y) Y7 Z8 T# x& N) b

% ]# i$ O% R0 I/ N        
               
( q3 I8 J- p- X0 m6 r" F                    
, c7 W/ s: _  a" Q' ?, M                        
                    
# r3 @5 X( d3 v8 h2 j, N* p+ i8 x6 H# E                    
本节主题回溯算法
更多算法深入聊聊KMP算法
我的主页蓝色学者的个人主页



文章目录
* t8 X' H7 @; g) u& n. r- s

一、前言

二、概念

三、例题

1.题目全排列

2.解题思路

回溯算法的本质

问题1

问题2

问题3
8 x$ c/ i/ R( m5 H* l2 E' n   
   

3.总结

4.参考代码
; R( n5 r6 Q5 ?8 g2 v- E8 n   

四、作业

五、结语
1 L) W& s" Q$ @3 _" R/ F6 `) ]0 y
) d7 ?. n8 L) z/ C7 e9 m) V
6 p' V" J: B. @4 u( P一、前言
$ V5 z5 w- O) g很开心又跟大家见面了今天我们来一起学习一下回溯算法的基本思想完成一道经典题目的讲解全排列之后我还会留下本节课的小作业感兴趣的话一起来看看把~

2 X3 k) a  `9 }) K2 ^3 I; ?二、概念
回溯算法又称试探法外文名backtrackingalgorithm这也是为什么我们经常在定义回溯函数的时候为函数取名为 backtracking 回溯算法正如其名在有多种选择的情况下回溯算法会试探性的挨个选择接着再回退到选择前的状态。

  d: E2 ^9 g) c$ F
/ U: O. ^9 V; E: I" t) \& C2 r 其实回溯算法本质上也是一个暴力算法
5 u/ U: K5 G; n

6 u9 H$ M/ R2 s" [6 X( y( U4 r为什么说回溯算法本质上也是暴力算法呢我们通过接下来的一个例题来为大家解释一下
7 u5 I3 T; V: X
5 i- \3 I$ @* h% r; Y1 Y三、例题
2 m3 I$ Q$ l1 V- }3 p1.题目全排列
全排列leetcode链接https://leetcode.cn/problems/permutations/
本题给定我们一个不含重复数字的数组 nums 返回其 所有可能的全排列可以按任意顺序返回答案。
1 J$ ?1 Z: X) O% q4 T

示例1
输入nums = [1,2,3]
5 h  m1 U6 L% n' P 输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
, Y% j. Y# q5 x: ?& C& U" H/ \ 示例2
' `/ u. n8 }8 @* |) @% k- @ 输入nums = [0,1]
输出[[0,1],[1,0]]
3 {0 x' B/ e' O0 C
- X4 G+ |2 G$ D7 A1 K
2.解题思路
, E* }) I  _' K5 W* R$ W全排列想必大家在初高中都应该接触过那么我们都会使用一种方法定住一项让后面交换位置从而达到目的比如


  o6 z9 Q8 `( u/ T: z! T( e- d 定住1那么还有2和3一种结果是{123} 交换位置得{132}
) `- H. d. ]0 i2 E8 z  F! b 定住2那么还有1和3一种结果是{213} 交换位置得{231}
定住3那么还有1和2一种结果是{312} 交换位置得{321}
7 y! C% h/ X- [/ ]% R" ~  S; S* n; P
& }0 ^4 U3 d6 n4 a/ P
$ d6 ]: A. S5 m$ ~, H5 @这样我们便得到了{123}的全排列
& C5 O& _1 G% R" G' l; L
* e1 u+ ~" n0 L) t7 \
) T# Q6 ]. l" _ 但是假如我们要求{1,2,3,4}的全排列呢
5 L7 v( S, R& W- c6 b/ Z3 G

很显然我们交换元素的逻辑就会变得复杂2和3交换完以后4怎么办很显然这样会让我们大脑短路如何才能求出呢
) J0 f- B) J6 Q! c7 R3 v9 @) V( L
7 A+ S7 A4 W7 L- B3 S5 g8 y! h

                 回溯算法引入
: |- G; g. ~* c( o, ?$ A! L
复制代码

回溯算法的本质
' ^/ P" f; x- f1 `其实回溯算法本质上也是一种暴力的算法他解决了我们在交换问题上的困惑还拿刚刚{123}的例子
2 r$ }  y5 j' ^% b$ H7 C

481cdcab61a5414ca4cfd5fd7e3b08b6.png (110.28 KB, 下载次数: 0, 售价: 4 金钱)

2023-1-19 12:24 上传

点击文件名下载附件
481cdcab61a5414ca4cfd5fd7e3b08b6.png

如图我将上述过程整理成了一张图片方便大家学习感悟在这里我想问大家两个问题


9 U; |8 x8 A6 @( \# F; b 1.第一次取1第二次怎么取2第三次怎么取3
$ f( \6 m# y3 N3 P; F2 y' H 2.什么时候该回溯
' c1 m$ e( h& o; Q6 G 3.回退到哪里


& ], G! j2 m! a% F1 L+ ?相信这两个问题搞清楚了你的回溯算法就算是听懂了下面我来一一回答一下这三个问题
- m8 X: W* ?9 D* E8 w
问题1
我们可以定义一个循环让此循环能够遍历完{123}

for(int i = 0;i 
[b] 
 1.我们只需要每次让下标为i位置的元素与第一个元素交换即可这样我们不就能拿到分别以123开头的元素了吗当我们确定了第一个元素剩下的元素应当也按照这样的逻辑进行交换注意此时就不再是与0号下标交换而是与第一个不确定位置的下标交换也就是first
3 ~: c4 A2 Q$ G, V/ j" b1 q  f% H8 f
 
: F4 O& y! \! |3 z/ o% u+ Z
 2.在固定好一个数字后我们需要依次确定其他数字所以要重复上述过程直到所有数字都被固定了因此我们采用递归的思路来完成。
* \; ^$ E! ?8 L; [2 |. H5 l( A! h# }
 
1 e" T" C2 v/ Q- R3 a: M- i' b
[/b] 
问题2 
[b] 
 当什么时候应该回溯呢按照上文的逻辑我们不难得出当得到与原数组相同长度的数组时我们就可以保存结果向上回退了
* g2 W( \* B& G' {" F7 p+ p2 z
 
[/b] 
, g! M" B4 l7 E9 _2 w" l; D/ I
问题3 
[b] 
" H; Y4 F4 ~0 x4 H$ g# j
 回退到哪里比如我们确定1后选择了2我们自然能确定{123}但我们还漏下了选择3之后确定{132}的情况自然要回退到没选择2的时候想想我们第一个问题不难得出我们交换后还要再交换回来这是回溯算法的精髓
1 y# A% g2 s! \: W
 
[/b] 
- d! ?4 b; b9 ~7 H2 M* [8 `
3.总结 
这道题目是一道很经典的回溯算法题目先把上面我回答的三个问题看清楚再去挑战这道题会轻松很多如果你对哪一步仍有疑问可以试着多看一下我上面画的图多回想上面的三个问题一定会有所收获。
7 Y9 J, H8 J" y, a- |# ^) B
 
" Q' q5 E. T7 V
4.参考代码 
[code]class Solution {
1 J, V' G4 b5 _, E+ F
public:
    void backtrack(vector& res, vector[i]& output, int first, int len)   
    {
        // 到达数组最大长度
        if (first == len) 
& j4 z# L& ?" o  n0 M
        {
4 ]+ e* i3 C$ d; t2 K8 ^* I
            res.emplace_back(output);
& w& T2 q% c/ J
            return;
$ L. \6 r+ t" r- ^" ~
        }
        for (int i = first; i 
            // 交换
2 s4 s- @5 u, u3 V: k/ E
            swap(output[i], output[first]);
7 q$ J* d6 `# [" M& U' P6 t
            // 递归确定下一个数
* o/ A, P: V( x* I
            backtrack(res, output, first + 1, len);
  L$ X3 w: S1 C0 @& h5 S
            // 交换回来
3 l0 ~" K! N/ H  \% H  O( D4 i9 R
            swap(output[i], output[first]);
+ E9 k! M& \' ^5 ^
        }
/ d3 X' j4 b. w
    }
4 J8 e6 h7 H. Z. ]& ^( H
    vector permute(vector[i]& nums) 
, W+ @+ ?4 O/ e$ t
    {
        vector res;
0 C! h, {' t, l1 a- v
        backtrack(res, nums, 0, nums.size());
        return res;
6 ?! k( B/ Z, m
    }
1 x. C. m" a+ l
};
0 R2 C6 s+ Y$ Y
复制代码

, V) w$ n" |8 R四、作业

( {6 U! f- k" X9 W, V; F: Z9 V2 ~ ?消化吸收完本次讲解的内容后大家可以试着去挑战两道题目
如果你还未熟练掌握回溯算法组合问题https://leetcode.cn/problems/combinations/
7 e1 \1 W. b, p% |  \9 h 如果你已熟练掌握了回溯算法N皇后
https://leetcode.cn/problems/n-queens/
之后的回溯练习文章里我还会详细讲解这两道题期待的话可以点一下收藏
3 {. I  x$ B0 F

  S$ _$ ?5 H7 v9 H* Z" q五、结语

到这里我们就学完了回溯算法里最经典的题目我们知道回溯算法其实也是一种暴力算法其实对于有些问题能够暴力写出就已经很不错了比如N皇后问题因此回溯算法也是很有必要掌握的


; l/ L8 S: @7 i" x/ ]  t) O: n
4 c5 V2 c* o7 j 如果你感觉有所收获的话可以 点赞+评论+收藏支持学者哦下次见

: O  A4 B0 d+ \
               
2 ^) M/ z  G7 W* \               
               
本文来源csdn，由Java吧转载发布，观点不代表Java吧的立场，转载请标明来源出处：https://www.java8.com