组合问题变式——选数（dfs）

代码随想录听课笔记1——回溯算法-CSDN博客

这是从1，2，3...,n个数字中选出k个数的组合，输出组合的全部可能的代码

//组合：返回1-n中所有个数为k的组合 1,2,3,4
#include<bits/stdc++.h>
using namespace std;
#define MAX 1010
int result[MAX];
//u表示选了几个数 
void dfs(int u,int n,int k,int startIndex){
	if(u==k){
		for(int i=0;i<k;i++){
			cout<<result[i]<<" ";
		}
		puts("");
		return;
	}
	for(int i=startIndex;i<=n;i++){
		result[u]=i;
		dfs(u+1,n,k,i+1);
	}
}

int main(){
	int n,k;
	cin>>n>>k;
	dfs(0,n,k,1);
	return 0;
}

上面的代码相当于选出了索引，比如1，2，3。我们只需要把n个整数放入一个数组中即可，然后相当于选出了数组的索引，通过数组的一一映射关系相当于选出了所对应的数字。然后把这些数字相加判断是否是素数即可啦！
 

//组合：返回1-n中所有个数为k的组合 1,2,3,4
#include<bits/stdc++.h>
using namespace std;
#define MAX 1010
int result[MAX];
int num[30];
int cnt = 0;
bool isPrime(int x) {
    if (x < 2) return false; // 0和1不是素数
    if (x == 2) return true;  // 2是素数

    // 只检查2到sqrt(x)之间的因子
    int limit = sqrt(x);     // 提前计算平方根
    for (int i = 2; i <= limit; i++) {
        if (x % i == 0) {
            return false;  // 如果能整除，说明不是素数
        }
    }
    return true;  // 没有找到因子，是素数
}
//u表示选了几个数 
void dfs(int u,int n,int k,int startIndex){
	if(u == k){
		int sum = 0;
		for(int i = 0;i<k;i++){
			sum += num[result[i]];
		}
		if(isPrime(sum))cnt ++;
		return;
	}
	for(int i = startIndex;i <= n;i ++){
		result[u] = i;
		dfs(u + 1,n,k,i + 1);
	}
}

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