1.DFS

DFS(i=0){
    if(得到一条解路径){
        输出;
        return;                          //该分支结束
    }

    for(第i步的所有可能j){
        a[i]=j; //选取一种可能
        DFS(i+1); //走下一步            //j个分支都return之后，函数结束
    }
}

2.回溯

回溯法是剪枝的暴力法。

剪枝函数包括两类:
1.使用约束函数，剪去不满足约束条件的路径；
2.使用限界函数，剪去不能得到最优解的路径。

将问题转化为解空间树，解空间树分为两种：排列树和子集树(组合树)。
排列树： 所给的问题是确定n个元素满足某种性质的排列。
子集树： 所给的问题是从n个元素的集合S中找出满足某种性质的子集。

递归形式

//一般要三个参数，a[]用来存储一条解路径，n为搜索深度，i为当前深度，如果要保存所有解，还需要一个参数来存储所有解路径
void fun(int a[], int n, int i){    //第i步的走法

  if(i==n){    //得到一条路径
    输出解路径a[n];
    return;
   }

   for(j=下界;j<=上界;j++){   //用j枚举第i步的可能走法
       if(j满足条件){  //剪枝，没有则为深度搜索
          取走j;
          a[i]=j;   //这两步紧密连接
          fun(a,n,i+1);   
          释放j;
        }
     }

}

1.输出n的排列

递归

先放置第1位置，再对后面n-1个位置全排列。(输出不是字典序)

void permutaion(int a[],int n,int i)  //a={1...n}，放置第i个位置，初始为0
{
    if (i==n) {
        for(int j=0;j<n;j++)
            cout<<a[j]<<" ";
        cout<<endl;
        return;
    }
                
    for(int j=i;j<n;j++) {   //第i个位置可放的是它及它后面的数，用j遍历之
        swap(a[i],a[j]); //该位置放置a[j]
        permutaion(a,n,i+1);  //开始下一位置
        swap(a[i],a[j]); //释放a[j]，回到原先状态
    }   
}

若含有重复数字，需要在swap之前判断a[j]是否在a[i,j-1]之间出现过，未出现时才进行那三步操作。

非递归

按字典序输出，初始a[n]为字典序最小的，找下一个字典序。有重复元素也不影响。
步骤：2找，1换，1逆
1，从后往前找第一个升序位置i，a[i]<a[i+1]，找不到时函数结束;（a[i]之后为降序）
2, 从后往前找第一个位置j(j在i后面)，a[j]>a[i];
3，交换a[i],a[j];
4, a[i]之后的元素逆序。

void print(int a[],int n){
    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';
    cout<<endl;
}

void reverse(int a[],int n,int strat){
    int l=strat,r=n-1;
    while(l<r){
        swap(a[l++],a[r--]);
    }
}


void permutaion(int a[],int n)  //a={1...n}。以a[i]开头，i初始为0
{
    if(n==1){
        cout<<a[0]<<endl;
        return;
      }
      
  int i,j;
  while(1){
        print(a,n);

        for(i=n-2;i>=0;i--){
            if(a[i]<a[i+1])
                break;
            else if(i==0)
                return;
        }
        for(j=n-1;j>i;j--){
            if(a[j]>a[i])
                break;
        }

        swap(a[i],a[j]);
        reverse(a,n,i+1);
  }
}

1.1 随机输出一个排列

    #include<time.h>
    #include<cstdlib> //生成随机数的头文件
 
    void randPermutaion(int a[],int n,int i){    
        srand((unsigned)time(NULL));

        for(int i=0;i<n;i++){  //每个位置随机放一个它及它之后的数
            int p=rand()%(n-i) + i;
            swap(a[i],a[p]);
        }
    }

2.输出n的组合（一个集合的所有子集）

第一个元素取或不取，确定之后，再对后面n-1个元素组合

void subsets(bool a[],int b[],int n,int i) //a为是否取的标记数组，b={1...n}为该集合
{
    if (i==n) {
        for(int j=0;j<n;j++){
            if(a[j])
                cout<<b[j]<<" ";
        }
        cout<<endl;
        return;
    }
                
    for(int j=0;j<=1;j++) {  //第i个元素，可以取或不取
        a[i]=j;
        subsets(a,b,n,i+1);  
    }
   
}

2.1.输出n的组合，且长度为m

取第一个元素，后面取m-1个；不取第一个元素，后面取m个

void subset(vector<int> ans,vector<int> a,int n,int m,int i){
    if(ans.size()>m) //元素个数超过，就停止向下递推，相当于剪枝
        return;
    if(i==n){  //扫描完数组
        if(ans.size()==m){  //元素个数等于m
            for(int j=0;j<m;j++)
                cout<<ans[j]<<" ";
            cout<<endl;
        }
        return;
    }
    //和上面一样，每个元素取或不取
    ans.push_back(a[i]);
    subset(ans,a,n,m,i+1);

    ans.pop_back();
    subset(ans,a,n,m,i+1);
}

3.八皇后

1,每行放且只放一个皇后：保证了不同行
2,八个皇后对应的列不相同：保证了不同列
例：0~7行的皇后所在的列为[0,1,2,3,4,5,6,7],一个全排列就保证了不同行，不同列。
3,两个皇后不在一条对角线：i-j != a[i]-a[j] && i-j != a[j]-a[i]

所以只要在全排列的代码中加一个判断条件即可。参考回溯。
或者枚举出所有排列，在一一判断是否满足条件，时间复杂度比回溯法稍微高。

#include<iostream>
using namespace std;

bool check(int a[],int i,int j){
    for(int k=0;k<i;k++){
        if(i-k==j-a[k]||i-k==a[k]-j)
            return false;
    }
    return true;
}

void permutaion(int a[],int n,int i)  
{
    if (i==n) {
        for(int j=0;j<n;j++)
            cout<<a[j]<<" ";
        cout<<endl;
        return;
    }
                
    for(int j=i;j<n;j++) {   
        if(check(a,i,a[j])){ //多了一个判断语句来剪枝。保证选取a[j]时，它和前面的皇后都不同对角线
            swap(a[i],a[j]); 
            permutaion(a,n,i+1);  
            swap(a[i],a[j]); 
        }
    }   
}

int main(){
    int a[]={0,1,2,3,4,5,6,7};
    permutaion(a,8,0);
    return 0;
}