回溯法本质是尝试所有的可能性,并把符合条件的可能记录下来,不符合的情况及时退出的一种方法。下面我们通过两个具体的题目来深刻理解回溯法的思想。
第一题:子集
题目分析:数组长度为n的数组的所有子集,其长度从0(空数组)到n(原数组)不等,因此我们可以使用回溯法来探寻不同长度子数组的所有可能性。
由于回溯法刚开始的时候理解起来有难度,所以我们首先来结合代码进行逐步分析。
为了更细致的总结其调用过程,我们将示例中长度为3的数组[1,2,3]
替换为长度为4的数组[1,2,3,4]
,以下为题目使用回溯法的ac代码:
nums = [1,2,3,4]
def backtrack(first=0, curr=[]):
# if the combination is done
if len(curr) == k:
output.append(curr[:])
return
for i in range(first, n):
curr.append(nums[i])
backtrack(i + 1, curr)
curr.pop()
output = []
n = len(nums)
for k in range(n + 1):
backtrack()
return output
为了方便理解其具体的调用过程,我们打印其每一步的操作,修改代码如下所示:
nums = [1,2,3,4]
def backtrack(first=0, curr=[]):
# if the combination is done
if len(curr) == k:
output.append(curr[:])
return
for i in range(first, n):
curr.append(nums[i])
backtrack(i + 1, curr)
curr.pop()
print(output)
output = []
n = len(nums)
for k in range(n + 1):
backtrack()
其部分输出如下所示:
[[], [1]]
[[], [1], [2]]
[[], [1], [2], [3]]
[[], [1], [2], [3], [4]]
[[], [1], [2], [3], [4], [1, 2]]
[[], [1], [2], [3], [4], [1, 2], [1, 3]]
[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4]]
[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4]]
[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3]]
[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4]]
[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4]]
[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3]]
...
[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]
接下来我们跟随其调用过程来看看他的具体实现过程:
首先创建数组output
来符合条件的子数组
然后进入for
循环:for k in range(n + 1):
,其中k表示子数组可能的长度,因此需要从0试探到n为止。
1. k=0
时:调用我们定义的回溯函数backtrack()
,接着进入回溯函数backtrack(0,[])
,因为此时k=0,curr=[]
,所以执行if
语句,output
中添加了子数组[]
,此时output= [[]]
。结束调用,返回主函数的for
循环。
2. k=1
时:调用回溯函数backtrack()
,(调用深度为1)接着进入回溯函数backtrack(0,[])
,因为此时k=1,curr=[]
,所以不执行if
语句,进入回溯函数中的for
循环for i in range(first, n):
,curr尝试添加数组中的第一个元素1,此时curr=[1]
,
(调用深度为2)接着调用backtrack(i + 1, curr)
,执行回溯函数backtrack(1, [1])
,因为满足if
条件,所以将当前的curr=[1]
添加入output
中,output=[[],[1]]
,结束深度为2的调用,返回深度为1的backtrack()
中继续执行。
(调用深度为1)curr.pop()弹出curr的最后一个元素,此时curr=[]
。
之前介绍的是for
循环for i in range(first, n):
中的第一次循环i=0的情况,剩下的循环执行过程与此完全相同,当执行完该循环后的output=[[],[1],[2],[3],[4]]
。
3. k=2
时:调用深度最高会达到3层。
第一层:主函数的for
循环for k in range(n + 1):
第三次循环,即k=2时,调用回溯函数backtrack()
,因为不满足if
条件,所以执行下面的循环for i in range(first, n)
,此时first=0,
curr
添加nums[0]
后,curr=[1]
。之后再次调用回溯函数backtrack()
,进入深度为2的调用。
第二层:依然不满足if
条件,执行下面的循环for i in range(first, n)
,此时first=1,
curr
添加nums[1]
后,curr=[1,2]
。再次调用回溯函数backtrack()
,进入深度为3的调用。
第三层:满足if条件,output
添加新的子数组[1,2]
,返回第二层调用。
之后完成第二层的for循环(此过程中一共进行了三次第三层深度的调用,分别添加了三个长度为2的子数组),此时output = [[],[1],[2],[3],[4],[1,2],[1,3],[1,4]]。此时还有一个关键点要注意一下,就是第三层调用添加完子数组[1,4]
后的执行情况。在添加完子数组[1,4]
后,返回第二层深度的回溯函数调用,此时cur=[1,4]
,执行完curr.pop
后curr= [1]
,但是这时要注意的是,第二层的回溯函数中的循环for i in range(first, n):
结束了,需要返回第一层循环for i in range(first, n):
中的调用部分,因此接下来执行的是第一层中的curr.pop,此时curr=[]。
接着继续进行第一层的循环for i in range(first, n):
。
当第一层循环也结束后,所有长度为2的子数组便均添加到output中了,接下来继续执行k=3和k=4的情况即可。
总结:
跟着分析完整个函数的执行过程后,再看一下回溯法给出的答案,我们不禁会发现,该结果是非常有规律性的,尤其是符合人的认知规律。
[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]
其实回溯函数中核心的就是如下所示的不断尝试,加进去若合适则记录下来(通过新调用的回溯函数最开始的if来实现),不合适则加入下一个元素继续尝试(用pop弹出并用append加入下一个)。
for i in range(first, n):
curr.append(nums[i])
backtrack(i + 1, curr)
curr.pop()