枚举+dfs题单

一、模板题

819. 递归求阶乘

#include <iostream>
using namespace std;
int f(int n)
{
    if(n==1) return 1;
    return f(n-1) * n;
}
int main()
{
    int n; cin >> n;
    cout << f(n);
    return 0;
}

94. 递归实现排列型枚举

#include <iostream>
using namespace std;
const int N = 25;
int n;
int a[N], st[N], f[N];
void dfs(int u)
{
    if(u == n) {
        for(int i = 0; i < n; i++)
            cout << f[i] << " ";
        cout << "\n";
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        // 当前这个数选没选
        if(st[i]) continue;
        st[i] = 1; f[u] = i;    // 选择当前这个数
        dfs(u + 1);
        st[i] = 0; f[u] = 0;    // 回溯
    }
}
int main()
{
    cin >> n;
    dfs(0);
    return 0;
}

92. 递归实现指数型枚举

#include <iostream>
using namespace std;
const int N = 25;
int n;
int f[N];
void dfs(int u, int start)
{
    for(int i = 0; i < u; i++)
        cout << f[i] << " ";
    cout << "\n";

    for(int i = start; i <= n; i++)
    {
        // 当前这个数选没选
        f[u] = i;    // 选择当前这个数
        dfs(u + 1, i + 1);
        f[u] = 0;    // 回溯
    }
}
int main()
{
    cin >> n;
    dfs(0, 1);
    return 0;
}

#include <iostream>
using namespace std;
int n;
int main()
{
    cin >> n;
    for(int i = 0; i < (1<<n); i++)
    {
        for(int j = 0; j < n; j++)
            if(i >> j & 1) cout << j + 1 << " ";
        cout << endl;
    }
    return 0;
}

93. 递归实现组合型枚举

#include <iostream>
using namespace std;
const int N = 25;
int n, m;
int f[N];
void dfs(int u, int start)
{
    if(u == m){
        for(int i = 0; i < u; i++)
            cout << f[i] << " ";
        cout << "\n";
        return;
    }
    
    for(int i = start; i <= n; i++)
    {
        // 当前这个数选没选
        f[u] = i;    // 选择当前这个数
        dfs(u + 1, i + 1);
        f[u] = 0;    // 回溯
    }
}
int main()
{
    cin >> n >> m;
    dfs(0, 1);
    return 0;
}

二、练习

5491. 选数

#include <iostream>
using namespace std;
const int N = 25;
int n, k, res = 0;
int a[N];
// 判断一个是否为质数
bool prime(int x)
{
    if(x==1) return false;
    if(x==2) return true;
    for(int i = 2; i <= x / i; i++)
        if(x % i == 0) return false;
    return true;
}
// u枚举的个数，start从哪个点开始选，sum前面枚举的数的和
void dfs(int u, int start, int sum)
{
    if(u == k) {
        if(prime(sum)) res++;
        return;
    }
    for(int i = start; i < n; i++)
        dfs(u + 1, i + 1, a[i] + sum);
}
int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    dfs(0, 0, 0);
    cout << res << endl;
    return 0;
}

1491. 圆桌座位

#include <iostream>
using namespace std;
int n, m, mp[100][100];
int st[100];
int dfs(int u, int fa)
{
    if(u == n) 
    {
        if(mp[fa][1]) return 0;
        else return 1;
    }
    int res = 0;
    for(int i = 2; i <= n; i++)
    {
        if(st[i] != 0 || mp[fa][i]) continue;
        st[i] = 1;
        res += dfs(u + 1, i);
        st[i] = 0;
    }
    return res;
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        mp[a][b] = mp[b][a] = 1;
    }
    cout << dfs(1, 1) << endl;
    return 0;
}

P2404 自然数的拆分问题

#include <iostream>
using namespace std;
const int N = 25;
int n, f[N];
// u枚举的个数，start从哪个点开始选，sum前面枚举的数的和
void dfs(int u, int start, int sum)
{
    if(sum >= n) {
        if(sum == n && u != 1) {
        	cout << f[0];
        	for(int i = 1; i < u; i++)
        		cout << "+" << f[i];
        	cout << endl;
		}
        return;
    }
    for(int i = start; i <= n; i++)
    {
    	f[u] = i;
    	dfs(u + 1, i, i + sum);
	}
}
int main()
{
    cin >> n;
    dfs(0, 1, 0);
    return 0;
}

P1219八皇后 Checker Challenge

#include<iostream>
using namespace std;
const int N = 100;
typedef pair<int,int> PII;
int h1[N], h2[N], cow[N];
int res = 0, f[N], n;
void dfs(int x)
{
	if(x==n + 1) 
	{
		res ++;
		if(res <= 3){
			for(int i = 1; i <= n; i++)
				cout << f[i] << ' ';
			cout << endl;
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(h1[i + x] || h2[i - x + 50] || cow[i]) continue;
		f[x] = i;
		h1[i + x] = 1; h2[i - x + 50]  = 1; cow[i] = 1;
		dfs(x + 1);
 		h1[i + x] = 0; h2[i - x + 50]  = 0; cow[i] = 0;
	}
}

int main()
{
	cin >> n;
	dfs(1);
	cout << res << endl;
}