dfs枚举问题

碎碎念：要开始刷算法题备战蓝桥杯了，一切的开头一定是dfs

定义

枚举问题就是咱数学上学到的，从n个数里面选m个数，有三种题型(来自Acwing)

1. 从 1∼n 这 n个整数中随机选取任意多个，输出所有可能的选择方案。
   

2. 把 1∼n这 n个整数排成一行后随机打乱顺序，输出所有可能的次序
   

3. 从 1∼n这 n个整数中随机选出 m个，输出所有可能的选择方案。
   

模版

我觉得这三个都可以由同一套板子来做

int path[N];
bool visited[N]
void dfs(int pos, int start, int n, int m)
//pos指的当前枚举位置
//start指开始的值(为了防止有的题目要求递增输入)
//n指的总元素
//m指的从n个里面挑m个进行枚举

这是通用的dfs定义,path存储每个位置放的元素的值，visited表示该元素是否访问过

逐个分析

• 对于这个，可以看到输出样例中他的一共有多少个数不固定，我们可以理解为从n个位置里面挑m个位置，本题没有要求以什么形式输出，为了规整，我默认写的是先1个位置，再两个位置，再三个位置，而且以升序排列
• 其dfs定义为

void dfs(int pos, int start, int m, int n)  //这个n又表示有多少个数
{if(pos > m){for(int i = 1; i <= m; i++)  //这个i循环的是位置，所以一直到mcout << path[i]<<" ";}else{for(int i = start; i <= n; i++)  //这个i循环的是元素的值，所以一直到n{if(!visited[i]){visited[i] = false;path[pos] = i;dfs(pos+1, i+1, m , n)  //这里是i+1,而不是start+1//后一个位置的值一定比当前位置值大，已知当前位置的值为i，则下一位置最低也得是i+1}}}
}int main()
{int n;cin >> n;for(int i = 1; i <= n; i++)dfs(1, 1, i, n)   //这个就是从n个位置选m个
}

第二个

这个就相当于从n个里面选n个，也不要求顺序了，则start可以当做没有

void dfs(int pos, int n)//这个n既代表位置，又代表元素的值
{if(pos > n){for(int i = 1; i <= n; i++){cout << path[i]<<" ";}cout<<endl;}else{for(int i = 1; i <= n; i++){if(!visited[i]){visited[i] = true;path[pos] = i;dfs(pos+1, n);  //是去下一个位置visited[i] = false;}}}
}
int main()
{cin >> n;dfs(1);
}

第三个

从n个元素里面选m个元素，位置最大也是m个，相当于第一种情况的m变式

void dfs(int pos, int start, int n, int m) //开始的值，当前位置
{if(pos > m)  {for(int i = 1; i <= m; i++)cout <<path[i]<<" ";cout << endl;}else{for(int i = start; i <= n; i++){if(!visited[i]){visited[i] = true;path[pos] = i;dfs( pos+1, i+1, n,m);visited[i] = false;}}}
}int main()
{cin >> n >> m;dfs(1, 1, n, m);return 0;
}

总结

• 边界条件比较的是位置， 下面的for循环是循环的元素的值，所以边界有时候不一样
• 如果要以元素的递增，则i = start， 后续要变化
• 其余的剪枝，回溯现场就不作解释了，csdn上有很多讲的超级明白的，我在这里就是对这三种题型做个总结