组合问题变式——选数（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;
}