1. 前言

本文将和大家一起聊聊递归回溯算法和原始穷举算法的内在关系，意在透过现象看本质，深入递归回溯算法的内在，真真切切看清楚其真面貌，而不仅限于套用算法模板。

回溯算法适用于如下的问题域：

• 问题可以分解成多个步聚。
• 每一步可有多个选择。
• 求解问题域的多种方案或其中的最优方案。

假设求解某问题共需要 n个步骤、而每一步可有的选择为m，根据乘法原理，则符合问题的方案应该有 n*m。如下图所示：

数学上的排列组合问题便是典型的此类问题。

排列问题描述：如从 1,2,3,4,5 这 5 个数字中选择 n(n<=5) 个数字进行重新排列，请问共有多少排列方案，当n=5时称为全排列。

本文将从求解全排列的原始穷举算法开始，一路讨索原始穷举算法和回溯算法之间的一致性。这里的一致性指回溯算法本质就是原始穷举算法，当然，两者之间会有思想层面的差异性。

2. 原始穷举算法

什么是原始穷举算法？

理论上讲，算法只有一种，便是穷举，但是，人是智慧性的，可通过发现待处理数据之间的逻辑关系，从而改进算法，减少穷举的次数，提升算法性能。

原始穷举算法也是一种静态处理算法。

静态做何解释？

不急，且先看如何使用原始穷举算法求解 1,2,3,4,5 这几个数字的全排列。

穷举的基本思想是先确定数据范围，然后对其进行筛选。5个数字的全排列穷举算法实现流程如下：

• 无论是哪一种排列方案，都需要找齐 5 个数字，说明每一种方案都需要分 5 步。如下图所示，每一次需要填满如下 5 个格间方算找出一种方案。

• 第一步可以从1,2,3,4,5 中选择出一个数字。如下图先选择数字 1。

• 因全排列数字不能重复使用，故第二步只能从没有选择的数字中再选择一个。

• 如此重复，至到完成后续步聚的填充。

如何编码实现？

必然是循环和条件分支语句上场，循环用来确定能查找的数字范围，条件分支进行筛选。

#include 
using namespace std;
int main(int argc, char** argv) {//统计总方案数量int count=0;//第一步可供选择数字范围为 1,2,3,4,5for(int i=1; i<=5; i++) {//确定第二步数字，可供选择数字范围为 1,2,3,4,5for(int j=1; j<=5; j++) {//因不能重复使用，需要排除if( j== i )continue;//第三步可供选择数字范围为 1,2,3,4,5，需要排除前面使用的for(int k=1; k<=5; k++) {if(k==j || k==i )continue;//第四步可供选择数字范围为 1,2,3,4,5，需要排除前面使用的for(int m=1; m<=5; m++) {if(m==j || m==i || m==k )continue;//第五步可供选择数字范围为 1,2,3,4,5，需要排除前面使用的for(int n=1; n<=5; n++) {if(n==j || n==i || n==k || n==m )continue;//计数count++;//到此，可以输出cout<

#include 
using namespace std;
/*
* pos:描述需要排列的数字个数
* 此函数本质就是封装了循环语句结构
*/
void fillNumber(int pos){for(int i=1;i<=5;i++){cout<

void fillNumber(int pos){for(int i=1;i<=5;i++){cout<

#include 
using namespace std;
/*
* pos:描述需要排列的数字个数
* num:已经在上一轮中选择好的数字
*/
void fillNumber(int pos,int num) {for(int i=1; i<=5; i++) {if(pos==2)//选择好了 2 个数字，递归出口，输出cout<

void fillNumber_(int pos,int num) {for(int i=1; i<=5; i++) {//本次选择不能和上次选择相同if(i==num)continue;//省略……}
}

#include 
using namespace std;
//数字的使用状态,初始为 0
int isUse[6]= {0};
//存储结果
int res[6]= {0};
//需要排列的数字个数
int num=2;
/*
*排列 
*/
void fillNumber(int pos) {for(int i=1; i<=5; i++) {if(isUse[i]==0) {//数字没有使用,填入结果res[pos]=i;//置为已用isUse[i]=1;if(pos==num) {//选择好了数字，递归出口，输出for(int j=1; j<=num; j++) {cout<

void fillNumber(int pos) {for(int i=1; i<=5; i++) {if(isUse[i]==0) {//数字没有使用,填入结果res[pos]=i;//置为已用isUse[i]=1;if(pos==num) {//选择好了所有数字，输出for(int j=1; j<=num; j++) {cout<

#include 
using namespace std;
int main(int argc, char** argv) {int target=21;int nums[8]= {2,3,5,7,11,13,17,19};//第一层循坏for(int i=0; i<8; i++) {//第二层循环for(int j=0; j<8; j++ ) {if( nums[j]==nums[i] )continue;if( nums[j]+nums[i]==21 ) {cout<

#include 
using namespace std;
int target=21;
//原始数字 1 2  3 4 5
int nums[8]= {2,3,5,7,11,13,17,19};
//状态数组：数字是否已经使用
int isUse[8]= {0};
//存储结果
int res[8];
//显示结果
int showAll() {int count=0;for(int i=0; i<8; i++) {if(res[i]!=0) {count++;cout<maxCount)maxCount=count;} else {//下一次循环(动态)fillNum(i+1,pos+1,target-nums[i]);}//回溯res[pos]=0;isUse[i]=0;}}
}
//测试
int main(int argc, char** argv) {fillNum(0,0,target);cout<<"有"<