nyoj 1058部分和問題（DFS） - acm1314－IT工程師數位筆記本

文章出處

部分和問題

時間限制：1000 ms | 內存限制：65535 KB

難度：2

描述

給定整數a1、a2、.......an，判斷是否可以從中選出若干數，使它們的和恰好為K。

輸入

首先，n和k，n表示數的個數，k表示數的和。
接著一行n個數。
（1<=n<=20,保證不超int范圍）

輸出

如果和恰好可以為k，輸出“YES”，并按輸入順序依次輸出是由哪幾個數的和組成，否則“NO”

樣例輸入

4 13
1 2 4 7

樣例輸出

YES
2 4 7

#include<cstdio>
#include<cstring>
bool vis[22], ok;
int a[22];
int n, k;
void dfs(int sum, int cur)
{
    if(sum==k)
    {
        if(!ok)
        {
            ok = 1;
            printf("YES\n");
        }
        for(int i=0; i<n; i++)
        if(vis[i])
        printf("%d ", a[i]);
        printf("\n");
        return;
    }
    for(int i=cur; i<n; i++)
    {
        sum+=a[i];
        vis[i] = 1;
        dfs(sum, i+1);
        vis[i] = 0;
        sum-=a[i];
    }
}

int main()
{
    while(scanf("%d%d", &n, &k)!=EOF)
    {
        for(int i=0; i<n; i++)
        scanf("%d", &a[i]);
        memset(vis, 0, sizeof(vis));
        ok = 0;
        dfs(0, 0);
        if(ok==0)
        printf("No\n");
    }
    return 0;
}