全探索アルゴリズム(brute force)と再帰処理

全探索アルゴリズムについて調べていたら、AIZU Online judgeにいい問題があったので、それを元に理解を深めます(個人的に)

問題は以下の通りです。

長さnの数列Aと整数mに対して、
Aの要素の中のいくつかの要素を足しあわせて
mが作れるかどうかを判定するプログラムを作成してください。
Aの各要素は１度だけ使うことができます。
数列 Aが与えられたうえで、質問として q 個の mi が与えれるので、
それぞれについて "yes" または "no" と出力してください。

制約が重くないために、
与えられた数値の全ての組み合わせを試せば問題が解けることになります。

制約

• n≤20
• q≤200
• 1≤Aの要素≤2,000
• 1≤mi≤2,000

問題の組み合わせ総数

与えられた数値が

1,3,5,7

だった場合、各々の数値をを使うか使わないかの選択になるので、
2^nの組み合わせになります。

再帰関数を使って、全探索を考える

以下引用になります。

1  makeCombination()
2    for i = 0 to n-1
3      S[i] = 0 // i を選択しない
4    rec(0)
5
6  rec(i)
7    if i == n
8      print S
9      return
10
11   rec(i + 1)
12   S[i] = 1 // i を選択する
13   rec(i + 1)
14   S[i] = 0 // i を選択しない

S配列をS[i] = 1の時その要素を選択する0は選択しないことを表す配列とします。
選択するかしないかを再帰関数により分岐させ、2^n - 1までのビット列を生成します。

この考え方を利用して、再帰関数を考えます。
solve(i,m)を「i番目以降の要素を使ってmを作れる場合trueを返す」という関数にすると、
solve(i,m)はより小さい部分であるsolve(i + 1,m)とsolve(i + 1,m - A[i])に分割することができます。
m - A[i]というところが、「i番目以降の要素を使う」に対応しています。

solve関数をc++で実装

再帰処理を行うsolve関数をc++で実装してみます。

// 入力値のmから選んだ要素を引いていく再帰関数
// 0なら組み合わせで生成できる数値
int solve(int i,int m){
    if(m == 0) return 1;
    if(i >= n) return 0;
    return solve(i + 1,m) || solve(i + 1,m - A[i]);
}

solveを使うmain関数を見ます。
入力された数列の各々の数値において、 与えられた数列で作りだせるかどうかをsolve関数を使って
判定しています。

int n,A[50];

int main(){
    int q,m;
    
    scanf("%d",&n);
    
    for(int i = 0;i < n;++i){
        scanf("%d",&A[i]);
    }
    
    scanf("%d",&q);
    
    for(int i = 0;i < q;++i){
        scanf("%d",&m);
        if(solve(0,m))printf("yes\n");
        else printf("no\n");
    }
    return 0;
}