最近班上的学生（小学5、6年级）要参加python的白名单比赛，从练习的结果来看，学生对于后面几道答题一直心有余悸，算法实在是太难了。
对于递归法，他们可以胸有成竹。对于回溯法，他们只能留下难过的泪水，因此怎么让学生听懂回溯法是重中之重。
而B站上或其他文章中，对于回溯法的讲解总让我感觉朦朦胧胧，因此自己尝试解开回溯法的面纱。
二、先从嵌套循环求排列
对于固定数量的排列组合，如从'abc'中选2个进行排列，可以使用2个for循环来解决
[Python] 纯文本查看 复制代码target = 'abc'
for x in target:
for y in target:
if x != y:
print(x, y)
得出的结果为
[Python] 纯文本查看 复制代码a b
a c
b a
b c
c a
c b
如从'abc'中选3个进行排列，可以使用3个for循环来解决
[Java] 纯文本查看 复制代码target = 'abc'
for x in target:
for y in target:
for z in target:
if x!=y and x!=z and y!=z:
print(x, y, z)
得出的结果为
[Python] 纯文本查看 复制代码a b c
a c b
b a c
b c a
c a b
c b a
三、思考
通过嵌套循环的确可以进行排列，但是我想从'abcdefg'中分别选3、4、5个进行排列，难道每次都要手动增加for循环次数吗？
而之前学习的递归法，函数通过自己调用自己好像可以帮助我解决这些问题，先尝试一下。
四、尝试使用递归法
我先创建一个方法，自己调用自己2次，然后遍历abc不就行了吗，并且使n传入的参数为n-1为嵌套循环
[Python] 纯文本查看 复制代码def abc_arrange(n, data):
# 遍历abc
for x in data:
print(x)
# 调用自己2次
for i in range(n):
abc_arrange(n-1, data) # 传入的参数为n-1为嵌套循环
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
abc_arrange(n, target)
结果
[Python] 纯文本查看 复制代码a
b
c
a
b
c
a
b
c
a
b
c
a
b
c
不行，思考一下嵌套循环里，大循环套着小小循环。
结果应该是：大循环的a对应小循环abc，大循环的b对应小循环abc，大循环的c对应小循环abc，那调用自身函数也是在循环里执行的，并且当n为0的时候，说明是最后一次嵌套循环，此时应该return
[Python] 纯文本查看 复制代码def abc_arrange(n, data):
if n == 0:
return
# 遍历abc
for x in data:
print(x)
abc_arrange(n-1, data)
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
abc_arrange(n, target)
结果为
[Python] 纯文本查看 复制代码a
a
b
c
b
a
b
c
c
a
b
c
这次好像可以了，请看下图
微信图片_20240519175241.png (24.92 KB, 下载次数: 0)
下载附件
2024-5-19 17:52 上传
现在只要想办法将大循环的abc与每个小循环的abc进行合并，就能得到aa,ab,ac,ba,bb,bc,ca,cb,cc
那就创建一个空列表为combination传入函数，用来存储合并结果
[Python] 纯文本查看 复制代码def abc_arrange(n, target, combination):
if n == 0:
print(combination) # 打印合并结果
return
# 遍历abc
for x in target:
combination.append(x) # 合并结果
abc_arrange(n-1, target, combination)
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
combination = []
abc_arrange(n, target, combination)
结果为
[Python] 纯文本查看 复制代码['a', 'a']
['a', 'a', 'b']
['a', 'a', 'b', 'c']
['a', 'a', 'b', 'c', 'b', 'a']
['a', 'a', 'b', 'c', 'b', 'a', 'b']
['a', 'a', 'b', 'c', 'b', 'a', 'b', 'c']
['a', 'a', 'b', 'c', 'b', 'a', 'b', 'c', 'c', 'a']
['a', 'a', 'b', 'c', 'b', 'a', 'b', 'c', 'c', 'a', 'b']
['a', 'a', 'b', 'c', 'b', 'a', 'b', 'c', 'c', 'a', 'b', 'c']
还不可以，一、元素重复了，二、合并结果长度不是2，再改一改
判断元素是否重复，重复就跳过
[Python] 纯文本查看 复制代码def abc_arrange(n, target, combination):
if n == 0:
print(combination) # 打印合并结果
return
# 遍历abc
for x in target:
if x in combination: # 如果已经存在元素就跳过
continue
combination.append(x) # 合并结果
abc_arrange(n-1, target, combination)
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
combination = []
abc_arrange(n, target, combination)
结果为
[Python] 纯文本查看 复制代码['a', 'b']
['a', 'b', 'c']
问题又出现了，大循环和小循环的abc都合并在一起了，导致conbination的列表结果只能是abc
想一想嵌套循环，大循环为a，小循环abc，已经排除重复出现的元素了，结果应该为ab,ac
说明进入小循环后，应该把combination里的小循环得到的元素删除，才能进入小循环中的下一次循环
同样的进入大循环中进入下一次循环后，也要把combination里的大循环得到的元素删除，才能进入大循环中的下一次循环
而在这个方法中，我在for循环和递归实现了嵌套循环，拿在循环后把conbianation删除最后一个元素不就可以了
这就是回溯的本质吧
[Python] 纯文本查看 复制代码def abc_arrange(n, target, combination):
if n == 0:
print(combination) # 打印合并结果
return
# 遍历abc
for x in target:
if x in combination: # 如果已经存在元素就跳过
continue
combination.append(x) # 合并结果
abc_arrange(n-1, target, combination)
combination.pop() # 在循环中进入下轮循环前删除最后一个元素
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
combination = []
abc_arrange(n, target, combination)
结果为
[Asm] 纯文本查看 复制代码['a', 'b']
['a', 'c']
['b', 'a']
['b', 'c']
['c', 'a']
['c', 'b']
排列成功了，用一个result的列表来存储所有的combination，储存需要添加combination的副本，和全局变量有关系
[Python] 纯文本查看 复制代码def abc_arrange(n, target, combination):
if n == 0:
print('combination', combination) # 打印合并结果
result.append(combination.copy()) # 要添加副本，不能直接添加combination
return
# 遍历abc
for x in target:
if x in combination: # 如果已经存在元素就跳过
continue
combination.append(x) # 合并结果
abc_arrange(n-1, target, combination)
combination.pop() # 在循环中进入下轮循环前删除最后一个元素
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
combination = [] # 储存合并结果
result = [] # 储存所有的合并结果
abc_arrange(n, target, combination)
print('result', result) # 打印所有的合并结果
结果为
[Python] 纯文本查看 复制代码combination ['a', 'b']
combination ['a', 'c']
combination ['b', 'a']
combination ['b', 'c']
combination ['c', 'a']
combination ['c', 'b']
result [['a', 'b'], ['a', 'c'], ['b', 'a'], ['b', 'c'], ['c', 'a'], ['c', 'b']]
成功了！试一下将排列换成组合，用集合排除重复的元素就可以了
[Python] 纯文本查看 复制代码def abc_arrange(n, target, combination):
if n == 0:
if not set(combination) in result:
print('combination', combination) # 打印合并结果
result.append(set(combination.copy())) # 要添加副本，不能直接添加combination
return
# 遍历abc
for x in target:
if x in combination: # 如果已经存在元素就跳过
continue
combination.append(x) # 合并结果
abc_arrange(n-1, target, combination)
combination.pop() # 在循环中进入下轮循环前删除最后一个元素
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
combination = [] # 储存合并结果
result = [] # 储存所有的合并结果
abc_arrange(n, target, combination)
print('result', result) # 打印所有的合并结果
结果为
[Python] 纯文本查看 复制代码combination ['a', 'b']
combination ['a', 'c']
combination ['b', 'c']
result [{'a', 'b'}, {'a', 'c'}, {'c', 'b'}]
感想
直接教我回溯法，教的我都懵了，果然从嵌套循环入手领悟到了回溯的本质，深度路径搜索算法和广度路径搜索算法都比这个容易理解
