这部分题分两个问题：1组合优化问题（顺序无关）。2排列选择问题（一般有个book[]数组记录搜索过没有）
注意：回溯法是一种完全搜索，有时进行适当的裁剪可以减少好多不必要的搜索步骤！
首先实现的是一个简单版本的回溯！
#include <vector> using namespace std; class Solution { public: vector<vector<int> > subsets(vector<int> &S) { vector<vector<int>> results; vector<int> item; results.push_back(item); generate(0,S,item,results); return results; } private: vector<int> S ; S.push_back(1); S.push_back(2); S.push_back(3); void generate(int i,vector<int>& nums,vector<int> &item,vector<vector<int>>&results) { if( i >nums.size()) //递归结束的条件 return; item.push_back(nums[i]);//依次添加下一个元素 results.push_back(item); //将当前生成的子集添加进results generate(i+1,nums,item,results); //递归执行上边的代码，直到return时进行下边的操作 item.pop_back(); //这里是回溯的关键 generate(i+1,nums,item,results); } };//这里是回溯的关键 generate(i+1,nums,item,results); } };
常用到的搜素算法有基于递归实现的深度优先搜素算法（DFS）和基于队列实现的广度搜素（BFS）；
需要说明：这两种算法和前面的算法没有本质的区别，都是一种完全遍历的算法，因此时间复杂度都先对较高，要想
改进就必须对回溯的过程就行修建，去掉一些不必要的步骤!
特别要注意的是DFS实现全搜索的过程是基于回溯的，回溯的过程是靠标记数组book[ ]来判断的，下边给出一个
简单的例子！
#include <iostream> #include <string.h> using namespace std; int visit[11],num[11]; int n; void dfs(int depth) { if(depth>n)//注意是大于号，不是大于等于，因为在等于的时候num[depth]还没有赋值 { for(int j=1;j<=n;j++) cout<<num[j]<<" "; cout<<endl; } else { for(int i=1;i<=n;i++) { if(!visit[i])//前提该数没有被访问 { visit[i]=1; num[depth]=i; dfs(depth+1); visit[i]=0;//返回原值，为新的排列做准备 } } } } int main() { while(cin>>n) { memset(visit,0,sizeof(visit)); dfs(1); } } visit[i]=0;//返回原值，为新的排列做准备 } } } } int main() { while(cin>>n) { memset(visit,0,sizeof(visit)); dfs(1); } }
