Luogu p1036 number selection

Topic link ： Selection

Knowledge point ： Combinatorial enumeration
Write here Recursive composite enumeration
The recursive search tree is as follows ：

Recursive composite enumeration template

void dfs(int u,int start)
{
    if(u == m)
    {
        for(int i = 0; i < m; i++) printf("%d ",path[i]);
        printf("\n");
        return;
    }
    
    for(int i = start; i <= n; i++)
    {
        path[u] = i;
        dfs(u+1,i+1);// Can not write start+1, Draw a recursive search tree .
    }
}

So let's talk about that dfs Inside pass start+1 and i+1 The difference between ：
start Represents the first number that can be selected at present .
i Representative means the number that can be selected （ No requirement is the first ）
Take an example to know why i+1 了 .

notes ：
1. The combinations thus assembled are sorted in dictionary order , Because first fill in the smallest number in the dictionary
2. Recursive composite enumerations do not require vis Array
3. No pruning here

AC Code ：

#include <iostream>

using namespace std;

const int N = 30;

int n, k;

int ans[N];
int obj[N];
int cnt;

bool check(int x)
{
    
	for (int i = 2; i <= x / i; i++)
		if (x % i == 0)
			return false;
	return true;
}

void dfs(int u,int start)
{
    
	if (u == k)
	{
    
		int res = 0;
		for (int i = 0; i < k; i++) res += ans[i];
		if (check(res)) cnt++;
		return;
	}

	for (int i = start; i < n; i++)
	{
    
		ans[u] = obj[i];
		dfs(u + 1,i+1);
	}
}

int main()
{
    
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> obj[i];
	dfs(0,0);
	cout << cnt;
}