回溯法有通用解题法之称，它可以系统的搜索一个问题的所有解或者任意解。它在问题的解空间树中，按深度优先策略从根节点出发搜索解空间树，算法搜索至解空间树的任意一个结点时，先判断该节点如（子树）是否包含问题的解，如果肯定不包含，则跳过对其子树的搜索，逐层向其根节点回溯。否则，则按照深度优先的策略搜索子树。 当回溯到根，且根节点的所有子树都已被搜索遍才结束。这种以深度优先方式系统搜索问题解的算法称为回溯法，适用于解决组合数较大的问题。
例如求集合{1，2，3}的子集问题的解空间树如下：
图示0代表该元素不在子集中，1代表该元素在子集中，显然可以看到该集合共有8个子集，因此可以按照回溯法的思想搜索它所有的子集。
回溯法搜索解空间树时，通常采用两种策略避免无效搜索，一种是用约束函数法在节点处剪去不符合要求的子树；第二种是用界限函数剪去得不到最有解的子树。
回溯法一般有两种实现方式，分别是递归回溯和迭代回溯。 递归回溯算法伪代码如下： void Backtrack(int t){ if(t > n) Output(x);//Output 记录或者输出可行解 else{ for( int i = f(n,t); i <= g(n,t); ++i){//f(n,t)和g(n,t)表示在当前结点未搜索过的子树的起始编号和终止编号 x[t] = h(i); if(constraint(t) && Bound(t)) Backtrack(t+1);//constraint和bound分别是约束函数和界限函数 } } } 迭代回溯算法伪代码如下： void IterativeBacktrack(void){ int t = 1; while(t > 0){ if(f(n,t) < g(n,t)){ for(int i = f(n,t); i <= g(n,t); ++i){//这个for 是遍历各个值的意思，实际中写成for循环会有逻辑错误 x[t] = h(i); if(constraint(t) && bound(t)){ if(solution(t)) Output(x);//solution 判断是否已经得到问题的解 else t++; } else t--; } } } } 最后贴上子集树（集合的所有子集）与排列树（求序列的所有排列）的递归算法和迭代算法： 求序列全排列算法实现： /* 设R={r1,r2,...rn}是要进行排列的n个元素.Ri=R-{ri}.集合X中元素的全排列记为 Perm(X).(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列 R的全排列可归纳定义如下: 当n=1时,Perm(R)=(r),其中r是集合R中唯一的元素; 当r>1时,Perm(R)由(r1)Perm(r1),(r2)Perm(r2).....(rn)Perm(rn)构成. 依此递归定义,Perm(R)的递归算法如下: */ #include <iostream> #include <algorithm> #include <vector> using namespace std; int cnt = 0; void Perm(int list[],int k,int m){ if(k == m){ cnt++; cout<<"cnt = "<<cnt<<endl; for(int i = 0 ; i <= m ; i++){ cout<<list[i]<<" "; } cout<<endl; } else{ for(int i = k ; i <= m; i++){ swap(list[k],list[i]); Perm(list,k+1,m); swap(list[k],list[i]); } } } /* 迭代实现，算法思想： 该问题的解空间是一棵排列树（可以看作子集树剪去了很多枝） 因此采用回溯法对解空间树进行搜索，得到想要的结果 对于长度为N的序列，可以看作深度为N的一棵树，依次对每一层搜索其子树节点 该例子中，第一层可选的子树节点有N个，第二层有N-1个知道最后一层叶子节点只有一个 是一棵典型的排列树 */ void Perm_iterative(int list[],int n){ int t = 0; vector<int> p = {-1,-1,-1,-1,-1};//p[i]表示在第i个位置（树第i层）排list[p[i]],list的第p[i]个元素 //set<int> bkt[n+1]; while(t >= 0){ int k = p[t]; while(find(p.begin(),p.end(),k) != p.end()) k++; if( k > n || t > n){//返回上一层节点时，清空子树状态 for(int i = t; i <= n; ++i) p[i] = -1; t--; continue; } p[t] = k; if( t >= n){//找到一个排列 cnt++; cout<<"cnt = "<<cnt<<endl; for(int i = 0 ; i <= n ; i++){ cout<<list[p[i]]<<" "; } cout<<endl; } else{ //cout<<"that"<<endl; t++; } } return; } int main(){ int x[] = {1,2,3,4,5}; cout<<"this is a test"<<endl; //Perm(x,0,4); Perm_iterative(x,4); } 求集合子集算法实现： /* 问题描述：对于一组各不相同的数字，从中任意抽取1-n个数字，构成一个新的集合。 求出所有的可能的集合。例如，对于集合{1,2,3}，其所有子集为{1}，{2},{3},{1,2},{1,3},{2,3}{1,2,3}， 给定一个数组（元素各不相同），求出数组的元素的所有非空组合（即数组的所有非空子集） 解法：位向量法。用一个辅助数组表示各个元素的状态。1表示在集合中，0表示不在数组中。递归地求解所有的子集。 算法描述如下：//这里的算法对空集也输出了，可修改之使得只输出非空集合。 下面代码分别用递归回溯和迭代回溯的方法实现了算法 */ #include <iostream> using namespace std; //递归实现 void getSubset(int list[],bool v[],int a,int b){ if(a == b){ for(int i = 0; i < b; i++){ if(v[i]) cout<<list[i]<<" "; } cout<<endl; return; } v[a] = true; getSubset(list,v,a+1,b); v[a] = false; getSubset(list,v,a+1,b); } //迭代实现 void getSubset_iterative(int list[],int n){ int t = 0;//t 代表解空间树的深度 bool v[n+1] = {false,false,false,false}; int init[n+1] = {0,0}; while( t >= 0){ if(2 > init[t]){ init[t]++; v[t] = !v[t]; if( t >= n ){ for(int i = 0; i <=n; i++){ if(v[i]) cout<<list[i]<<" "; } cout<<endl; } else{ ++t;//进入下一层 } } else{ //回溯至上一层，并将该层的状态重置，一定要重置 init[t] = 0; --t; } } } int main(){ int li[] = {1,2,3,4}; bool v[] = { false,false,false,false}; getSubset(li,v,0,4); getSubset_iterative(li,3); } 两段代码coding.net地址: https://git.coding.net/Mansion/Backtrace_IterativeVSRecursive.git
