「部分和問題」 競プロ例題 #1

部分和問題

整数 a_1, a_2,・・・, a_n が与えられる。その中からいくつか選び、その和を丁度kにすることができるかを判定する。

例1

• 入力

n=4
a={1,2,4,7}
k=13

• 出力

Yes

例2

• 入力

n=4
a={1,2,4,7}
k=15

• 出力

No

アルゴリズム

a_1 から順に加えるかどうかを決め、n個全てについて決め終わったらその和がkに等しいかを判定する。

回答例

static int n = 4;
static int a[] = {1, 2, 4, 7};
static int k = 15;

//iまででsumを作って、残りi以降を調べる
static bool dfs(int i, int sum) {
    //n個決め終わったら、今までの和sumがkと等しいかを返す
    if ( i == n ) return sum == k;
    
    //a[i]を使わない場合
    if (dfs(i + 1, sum)) return true;
    
    //a[i]を使う場合
    if (dfs(i + 1, sum + a[i])) return true;
    
    //a[i]を使わないに関わらずkが作れないのでfalseを返す
    return false;
}

static void solve_partial_sum() {
    if (dfs(0 ,0)) printf("Yes\n");
    else printf("No\n");
}

main関数でsolve_partial_sum()関数を実行する。