从n个数中选k个数（组合问题）

不降原则：选出的数全部保证是升序，这样就可以避免选重。

eg：1 2 3 4 5

我们可以选：

1 2 3

1 2 4

1 2 5

然后把第二位的2加1变成3，因为是升序

1 3 4

1 3 5

再把3加1变成4

1 4 5到这里以1开头的的组合就全部枚举完了，接下来就以2开头，因为时刻要满足是升序

2 3 4

2 3 5

2 4 5

3 4 5这里就把这5个数全部枚举完了。

这道题重点就是选数然后判断结果是否为质数

选数的过程就用了不降原则，利用递归实现

#include<iostream>
#include<algorithm>
using namespace std;
int a[100] = { 0 };
int n, k;
int sum = 0;
int ans = 0;
bool f(int sum)//判断质数
{if (sum == 2)return true;for (int i = 2; i < sum; i++){if (sum%i == 0){return false;}}return true;}
void dfs(int m,int sum ,int z)//传第一个数组下标，和选k个数，m是记录选了几个数
{if (m == k)//一旦已经选好了三个数就必须回溯{if (f(sum)){ans++;}return;//如果不在这个地方回溯的话，还会继续执行下面的语句m的值就会出错 return控制在哪个地方回溯}//没进入递归之前就是把选的第一个数都循环一遍，也是递归终止的条件for (int i = z; i <= n; i++)//进入第二个递归后就相当于把要选的第二个数全部都循环了{dfs(m + 1, sum + a[i], i + 1);}return;
}
int main()
{cin >> n >> k;for (int i = 1; i <= n; i++){cin >> a[i];//要保证是升序排放在数组中}sort(a,a + n+1);dfs(0,0,1);cout << ans;return 0;
}