选数
https://www.luogu.com.cn/problem/P1036

#include <bits/stdc++.h>
using namespace std;
int n,k,a[30];
long long ans;
bool isprime(int a){
    for(int i=2;i*i<=a;i++){
        if(a%i==0) return false;
    }
    return true;

}
void dfs(int m,int sum,int st){
    if(m==k){
        if(isprime(sum)) ans++;
        return;
    }
    for(int i=st;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];
    dfs(0,0,1);
    cout<<ans;
    return 0;
}

覆盖墙壁
https://www.luogu.com.cn/problem/P1990

#include <bits/stdc++.h>
using namespace std;
//f[N] 铺满前N*2面积的墙的方案数
//G[N] 铺满前（N+1）*2的面积的墙，但是第（N+1）列有一个瓷砖已经被铺过
//f[N]=f[N-1]+f[N-2]+2*G[N-2]
//G[N]=f[N-1]+G[N-1]
int f[1000010],g[1000010];
const int mod=10000;
int main(){
    int n;
    cin>>n;
    f[0]=1;
    g[0]=0;
    f[1]=1;
    g[1]=1;
    for(int i=2;i<=n;i++){
        f[i]=(f[i-1]+f[i-2]+2*g[i-2])%mod;
        g[i]=(f[i-1]+g[i-1])%mod;
    }
    cout<<f[n];
    return 0;
}

自然数的拆分问题
https://www.luogu.com.cn/problem/P2404

#include <bits/stdc++.h>
using namespace std;
int n,m,a[20]={1},cnt=1;
void print(int t){
    for(int i=1;i<t;i++)cout<<a[i]<<"+";
    cout<<a[t]<<endl;
}
void dfs(int cnt){
    for(int i=a[cnt-1];i<=m;i++){
        if(i==n)
            continue;
        a[cnt]=i;
        m-=i;
        if(m==0) print(cnt);
        else dfs(cnt+1);
        m+=i;
    }
}
int main(){
    cin>>n;
    m=n;
    dfs(1);
    return 0;
}