目录
递归实现指数型枚举
题目描述
运行代码
#include<iostream>
using namespace std;
int n,a[17],m;
void p(int n)
{
if(!n)return;
p(n/10);
cout<<n%10;
return;
}
void dfs(int i)
{
if(i>n)
{
for(int j=1;j<=m;++j)
{
p(a[j]);
cout<<" ";
}
cout<<endl;
return;
}
dfs(i+1);
a[++m]=i;
dfs(i+1);
m--;
return;
}
int main()
{
cin>>n;
dfs(1);
return 0;
}
代码思路
p函数用于将一个整数按位输出，通过递归的方式逐位取出并输出。dfs函数是深度优先搜索的主要函数。- 从
1开始进行深度优先搜索，当搜索到超过给定的n时，就输出当前已选择的数字序列。 - 在搜索过程中，有两种选择：一种是不选择当前数字，直接进入下一层搜索（
dfs(i+1)）；另一种是选择当前数字，将其添加到数组a中（通过递增m并赋值），然后再进行下一层搜索（dfs(i+1)），之后再回溯（通过m--恢复状态）。通过深度优先搜索生成并输出所有可能的数字组合情况。
递归实现组合型枚举
题目描述
运行代码
#include <iostream>
#include <vector>
using namespace std;
vector<int> a;
int n,m;
void dfs(int x)
{
if( a.size() == m )
{
for (int i = 0; i < a.size(); i++)
{
cout << a[i];
if( i != a.size() - 1 ) cout << ' ';
}
cout << '\n';
return;
}
if( a.size() > m || a.size() + n - x + 1 < m )
return;
a.push_back(x);
dfs(x+1);
a.pop_back();
dfs(x+1);
}
int main()
{
cin >> n >> m;
dfs(1);
return 0;
}
代码思路
变量定义:
vector<int> a;用于存储当前搜索路径上的数字，即当前组合。int n, m;分别表示可选择的数字范围（1到n）和每个组合需要的数字个数。主函数main():读入用户输入的n和m，然后调用
dfs(1)开始深度优先搜索，从数字1开始探索所有可能的组合。函数dfs(int x):
- 基础情况：如果当前组合
a的大小等于目标组合长度m，说明已经找到一个有效的组合，这时遍历并打印a中的所有数字，然后返回。 - 剪枝：如果当前组合的大小已经超过目标长度
m，或者即使把剩下的所有数字都加入当前组合也无法达到目标长度，说明此路不通，直接返回。 - 递归搜索：先做选择：将当前数字
x加入到组合a中，然后递归调用dfs(x+1)继续搜索下一个数字。撤销选择：在递归调用返回后，从组合a中移除最后一个数字（即撤销之前的选择），然后继续尝试下一个可能的数字，即再次调用dfs(x+1)。
- 基础情况：如果当前组合
程序能够遍历所有可能的组合，而不会重复，并且有效地跳过了不可能构成有效组合的搜索路径，这就是剪枝操作的作用，保证了算法的高效执行。
递归实现排列型枚举
题目描述
运行代码
#include<iostream>
#include<string>
#include<bits/stdc++.h>
using namespace std;
int n = 0;
int arr[10];
void FN(string & s) {
if (s.size() < 2 * n) {
for (int i = 1; i <= n; ++i) {
if (arr[i] == 0)
continue;
s += to_string(i) + " ";
arr[i] = 0;
FN(s);
s.pop_back();
s.pop_back();
arr[i] = 1;
}
return;
}
s.pop_back();
cout << s << endl;
s += " ";
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
arr[i] = 1;
}
string s;
FN(s);
return 0;
}代码思路
全局变量定义:
int n: 存储用户输入的整数，用于确定序列中数字的取值范围（1到n）。int arr[10]: 记录每个数字是否已被使用。初始化为1，表示所有数字都可以被使用。函数FN(string &s):
- 参数：
string &s是一个引用类型字符串，用于构建当前搜索路径上的序列。 - 基本思路：递归生成序列，当序列长度达到
2*n时，输出该序列。 - 递归条件：若
s.size()小于2*n，则继续添加数字。遍历1到n之间的数字，检查当前数字是否可用（arr[i]==1）。回溯：从s中移除刚添加的数字及其尾随的空格，并恢复数字的可用状态(arr[i]=1)。递归调用FN(s)继续构建序列。若可用，则将其转换为字符串形式添加到s中，并标记该数字已使用(arr[i]=0)。 - 输出条件：当
s的长度达到2*n时，从s中移除最后一个空格，输出序列，并在序列末尾添加一个空格准备下一轮的添加（虽然这里的添加空格在最终输出时并无实际作用）。
- 参数：
主函数main():读取用户输入的
n。初始化数组arr，允许所有数字最初都被使用。调用FN(s)开始递归生成并输出所有满足条件的序列，初始传入一个空字符串s。
利用深度优先搜索遍历所有可能的序列组合，并通过数组arr跟踪每个数字的使用状态，确保序列中任意两个相邻数字不相同。
