如何通过回溯法输出全排列？C++回溯代码回退逻辑疑问求解

你觉得疑惑的核心，是把递归最末端的退出动作，当成了整个回溯流程的终止动作——实际上每一层递归都有自己独立的for循环，只要当前层没把所有可选的i值遍历完，就会在拿到下一层的返回值后继续往下跑循环，不会直接跳回最外层。

每一层递归的实际执行流 #

代码里的递归是层层嵌套的，每一层perm(n)跑起来的步骤没有你想的那么复杂：

• 先判断如果n等于N，直接输出当前数组的排列然后返回
• 没到终止条件就进入for循环，从i=0开始逐个试选元素：
  • 碰到已经被标记使用的元素（flag[i]为true）就直接跳过
  • 选中当前i放到a[n]的位置，把flag[i]设为true
  • 调用perm(n+1)，进入下一层选位置放元素
  • 等下一层所有流程跑完、返回当前层之后，做现场清理：把刚才选的i对应的flag改回false
  • 执行i++，试下一个元素，直到i遍历到N，当前层的函数才会退出，把控制权交回给上一层

也就是说，你提到的“n=N时返回、把n=N-1层的flag置为false、i跑到N-1跳出循环”，只是最靠近递归终止点的perm(N-1)这一层跑完所有循环后的退出动作，这时候控制权是交回给调用它的perm(N-2)，根本不会直接跳过中间层一路退到最开头。

拿N=2的小例子跑一遍全流程 #

空讲逻辑容易懵，我们用最简单的N=2场景，初始flag数组全是false，从最外层调用perm(0)开始逐步行走：

1. 进入perm(0)，n=0没到终止条件，循环从i=0开始
   • i=0：flag[0]是false，设置a[0]=0，flag[0]=true，调用perm(1)
2. 进入perm(1)，n=1没到终止条件，循环从i=0开始
   • i=0：flag[0]为true，跳过
   • i=1：flag[1]是false，设置a[1]=1，flag[1]=true，调用perm(2)
3. 进入perm(2)，n==N，输出排列0 1，return回到perm(1)
   • 执行清理逻辑：打印i=1，把flag[1]置为false
   • 循环i++到2，不满足i<N的条件，perm(1)执行完，return回到perm(0)
4. 回到perm(0)，执行清理逻辑：打印i=0，把flag[0]置为false
   • 循环i++到1
   • i=1：flag[1]是false，设置a[0]=1，flag[1]=true，调用perm(1)
5. 再次进入perm(1)，n=1，循环从i=0开始
   • i=0：flag[0]是false，设置a[1]=0，flag[0]=true，调用perm(2)
6. 进入perm(2)，输出排列1 0，return回到perm(1)
   • 执行清理逻辑：打印i=0，把flag[0]置为false
   • 循环i到1，flag[1]为true，跳过；i到2，perm(1)执行完，return回到perm(0)
7. 回到perm(0)，执行清理逻辑：打印i=1，把flag[1]置为false
   • 循环i++到2，perm(0)执行完，整个流程结束

你会发现，从n=N-2层往回走的过程，根本不是“直接跳过循环回退”，而是每一层在拿到下一层的返回值后，都会接着试当前位置下一个没被选过的元素，重新进入下一层递归生成新的排列。

对应解答你的具体疑问 #

• 你提到“当n等于N时，函数会返回到调用位置并将flag[n-1]置为false，此时i取值为N-1并跳出循环”：这一步只是最末端的perm(N-1)层跑完当前分支的所有试选后的退出动作，退出后把控制权交回给上一层，不是整个流程结束。
• 上一层perm(N-2)收到返回值后，会先完成当前选中元素的flag清理，然后执行i++：如果当前i没遍历完，就选新的元素放到a[N-2]位置，再次调用perm(N-1)，生成分支下的所有排列。
• 这个“下一层跑完→上一层清理现场→上一层试下一个可选选项→再进入下一层”的流程会一直向上延伸，直到最外层的perm(0)把所有i值都遍历完，才会结束整个流程。

如果你实际跑代码只输出了N-1个元素的全排列，可以排查两个常见问题：

• 全局的flag数组有没有正确初始化为全false
• 调用perm的时候传入的初始参数是不是0，N的赋值是不是和a、flag数组的长度匹配

内容的提问来源于stack exchange，提问作者Riyo