dfs 实现排列型、组合型、指数型枚举

1、排列型枚举

大家喜闻乐见，经常写的全排列。不做赘述。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n;
int path[20];
bool vis[20];

void dfs(int step){
  if(step == n + 1){
    for(int i = 1; i <= n; i ++) cout << path[i] << " ";
    cout << endl;
    return;
  }
  
  for(int i = 1; i <= n; i ++){
    if(!vis[i]){
      vis[i] = 1;
      path[step] = i; 
      dfs(step + 1);
      path[step] = 0; 
      vis[i] = 0;
    }
  }
}

void solve(){
  cin >> n;
  dfs(1);
}

int main(){

  solve();
  
  return 0;
}

2、组合型枚举

这里相较于全排列，大家估计甚少写过了。变化了不止一点。

1.有了长度的限制

2.递增性

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n, length;
int path[26];

void dfs(int step, int start){
  if(step == length + 1){
    for(int i = 1; i <= length; i ++) cout << path[i] << " ";
    cout << endl;
    return;
  }
  
  for(int i = start; i <= n; i ++){
    path[step] = i; 
    dfs(step + 1, i + 1);// i + 1 ? 当前用了数x，下一个必须从数x + 1开始填   //保证递增性
    path[step] = 0; 
  }
}

void solve(){
  cin >> n >> length;
  dfs(1, 1);
}

int main(){
  solve();
  
  return 0;
}

3、指数型枚举

这个地方有个小坑，就是这个空行。可以直接单独输出一行空行也行。或者从0---n递归也有一行空行（一般从1---n递归）

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n;
int path[26];

void dfs(int step, int start, int length){
  if(step == length + 1){
    for(int i = 1; i <= length; i ++) cout << path[i] << " ";
    cout << endl;
    return;
  }
  
  for(int i = start; i <= n; i ++){
    path[step] = i; 
    dfs(step + 1, i + 1, length); //这里变化又多了一个限制
    path[step] = 0; 
  }
}

void solve(){
  cin >> n;
  for(int i = 0; i <= n; i ++){//妙在这里的变化，长度的变化，递增的变化。      //0开始只是为了过题
    dfs(1, 1, i);
  }    
    
}

int main(){
  solve();
  
  return 0;
}