P1036 选数

这道题题目本身并不难，递归写法也很简单。难点在于判重，虽然题目很基础，但是，事实上很多难的题目都是在基础之上，这道题做回了，实际上很多题目都能触类旁通，我之前因为去重的问题被逼死了…

下面画不下了，凑合看8~，从图中可以看到，这样写递归会有很多的重复，就比如3 7 12 和7 12 3 就是重复了，当然你也把所有满足条件的都保存起来，然后每满足一个就判断之前保存的所有结果中是否有和其重复的，但是这样效率太差了，数据一大肯定会wa掉，我们可以这样考虑

3 7 12

3 7 19

3 12 19

7 12 19

可以发现，我们这里的是顺序枚举的，所以不会出错，同理我们在程序中也可以这样来做~，用index来表示当前要选的数字

下面是AC代码：

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
#define  Max 666
int a[Max];
int b[Max];
int n,k,res=0;
bool is_prime(int n); //判断是否为质数
void dfs(int count,int  index);
    int main()
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        dfs(1,1);
        cout<<res<<endl;
        return 0;
    }


    void dfs(int count,int  index)
    {
        if(count==k+1)
        {
           int sum=0;
           for(int i=1;i<=k;i++)
           {
               sum+=b[i];
           }
           if(is_prime(sum))
           {
               res++;
           }
           return ;
        }

        for(int i=index;i<=n;i++)
        {
            b[count]=a[i];
            dfs(count+1,i+1);
        }
    }

    bool is_prime(int n) //判断是否为质数
    {
       if(n<=1)
       {
           return  false;
       }
       else
        {
            for(int i=2;i<=sqrt(n);i++)
            {
                if(n%i==0)
                {
                    return false;
                }
            }
            return true;
        }
    }