DFS

一般形式：
DFS(某状态){
如果搜出一种结果 返回；
在所有能做出的选择中{
做出该选择并记录该选择做过；
DFS（选择后的状态）
取消该选择以及对该选择的记录；
}
}

• 一、 全排列
  输入n，按字典输出所有1-n的全排列，n不超过10
  输入3，输出{1,2,3}，{1,3,2}，{2,1,3}，{2,3,1}，{3,1,2}，{3,2,1}

#include
#include
using namespace std;
int n;
vector ans;
void show(){
	for(int i=0;i>n;
	dfs(1);
	return 0; 
}

• 二、 next_permutation
  生成下一个全排列并判断是否生成了所有n！个排列

#include
#include
#include
using namespace std;
int n;
vector ans;
void show(){
	for(int i=0;i>n;
	for(int i=1;i<=n;i++){
		ans.push_back(i);
	}
	do{
	   show();	
	}while(next_permutation(ans.begin(),ans.end()));
	return 0;
}

• 三、 子集合
  {1 ,2,3}需输出{ },{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}
  N个元素的子集有2^n个

#include
#include
using namespace std;
int n;
vector ans;
void show(){
	for(int i=0;i>n;
	dfs(1);
	return 0;
}