整数a1,a2,a3,a4,...からn個選んで足すと値kになるかどうかの判定

[うしくん]

整数a1,a2,a3,a4,...からn個選んで足すと値kになるかどうかを判定するプログラムというのを練習しているのですが、
１日考えたんですが結局どう読んだらいいのか理解できませんでした。プログラムは下記のものです。
ちょこっと日本語の注記も書かれていますが、何をいっているのかさっぱりです。

コード:

#include <iostream>
#include <cstdio>

const int MAX_NUM = 20;
int a[MAX_NUM];
int n, k;

//iまででsumを作って、残りi以降を調べる
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;
}
	
int main () {
// data input
	std::cin >> n;
	for(int i =0; i <n; i++){
		std::cin >> a[i];
	}
	std::cin >> k;
	
//data output	
	if (dfs(0,0)) printf("Yes\n");
	else printf("No\n");
    return 0;
}

どなたか、このプログラムを説明していただけませんか？
なにとぞヨロシクお願いします。

[h2so5]

具体的にどの部分が分からないのですか？

main()の中が分からないのか
bool dfs()の中が分からないのか
それともif (dfs(i + 1, sum))の部分が分からないのか
もう少し詳しく言っていただけると助言しやすいです。

[うしくん]

bool dfs の中全部です。なにやってるのかほどんどわかりません。
各要素の意味くらいは多分理解しているとおもっていますが。たとえば一行目はiがnならばsumの値がkに等しいかどうか見て等しければtrue等しくなければfalseを返す、とか。
ですがそれがこの問題と同関係があるのか全くわかりません。恥ずかしながら。
ヨロシクお願いします。

[うしくん]

この掲示板は編集不可でしょうか？やり方がよくわからないので連投します。
もう少し捕捉しますと、
入力がn= 4 a={1,2,4,7} k =13 とします。

//iまででsumを作って、残りi以降を調べる

//n個決め終わったら、今までの和sumがkと等しいかを返す
これは、たとえば、i=0までsumを作る場合を考えてみました。
これは２、３番目のifに依存しているところまで分かりました。

//aを使わない場合
a[0]を使わない場合ということになるので、”iまででsumを作って”という作業終了？でもコードは再帰してます。よくわかりません。

//aを使う場合
i=0を入れると、dfs(1,1)で再帰します。”iまででsumを作って”という作業終了？なにをしているのか、分かりません。

[h2so5]

登録ユーザーでないと編集はできません。

//aを使わない場合
a[0]を使わない場合ということになるので、”iまででsumを作って”という作業終了？でもコードは再帰してます。よくわかりません。

a[0]を使わなくても、a[1]やa[2]..を使う場合があるので、継続します

//iまででsumを作って、残りi以降を調べる
という表現は紛らわしい気がしますね。i=nになるまで再帰し続けます。

ちなみに、内部ではこんな探索をしているようです。

Input:
4
1
2
4
7
13

訂正：使用と不使を入れ替えて読んでください。間違えました(-_-;)

a[0](1)使用->a[1](2)使用->a[2](4)使用->a[3](7)使用->合計:0
　　　　　　　　　　　　　　　　　　　　　　　　　　a[3](7)不使->合計:7
　　　　　　　　　 　　　　　　　　a[2](4)不使->a[3](7)使用->合計:4
　　　　　　　　　　　　　　　　　　　　　　　　　　a[3](7)不使->合計:11
　　　　　　　　　a[1](2)不使->a[2](4)使用->a[3](7)使用->合計:2
　　　　　　　　　　　　　　　　　　　　　　　　　　a[3](7)不使->合計:9
　　　　　　　　　　　　　　　　　a[2](4)不使->a[3](7)使用->合計:6
　　　　　　　　　　　　　　　　　　　　　　　　　　a[3](7)不使->合計:13

Output:
Yes

[うしくん]

返信ありがとうございます　h2so5さん。

一日調べてほとんどわからないままだったんですが、質問後に何も考えずに要素が２つとかで再帰をたどってみたりしてたら、だんだんわかってきました。
丁度レスいただいたように、結局、（後で再帰する）関数を全てのパターンに対して実行し尽くして、その後末端のsumの判定（一つ目のif）でtrueがあったらそれを戻していく作業ですね。１つでもtrueがあれば確かに最終判定までできそうです。

ただ、このプログラムで判定ができることは理解できそうな予感ですが、依然分からないのは、それは結果論のように見えるということです。
ここに合ったプログラムを走らせたら偶然うまくこの問題の答えがだせただけのような気がしています。

どう考えてこういうプログラムを構成していけばいいのか、ということを教えていただければ助かります。

[うしくん]

訂正　ここに合ったーー＞ここに在った

[kimuchi]

このプログラムではわざわざ再帰を用いているようですが、
実際に行っている処理は、入力する数の個数ｎを指定して、入力する数を全て足し、足した数が後に入力した数ｋと等しいか等しくないかの判定ですから、コードで示せば

コード:

int main () {
    int n,a,k,m=0;
// data input
    std::cin >> n;
    for(int i =0; i <n; i++){
        std::cin >> a;
        m += a;
    }
    std::cin >> k;
    
//data output   
    if (m==k) printf("Yes\n");
    else printf("No\n");
    return 0;
}

こんなものだと思います。おそらくこのプログラム自体にそんなに意味はなく、再帰を用いたサンプルとしての意味合いが強いのではないでしょうか。

追記：
こんなことを書いてしまいましたが、a5uaさんの書かれたものが正しいプログラムの解釈ですので、
そちらをご覧になって下さい。スレ汚し失礼いたしました。

[a5ua]

整数a1,a2,a3,a4,...からn個選んで足すと値kになるかどうかを判定する

とありますが、プログラムを見る限り、これは、
整数a1,a2,a3,a4,...からn個以下の数字を選んで足すと値kになるかどうかを判定する
プログラムだと思います。

本題ですが、dfsという名の通り「深さ優先探索 (depth-first search)」という考え方を身につける必要があります。
今回の問題では、「i番目に注目していて、今までの合計がsumになっている」という状況を1つの状態とします。
そうすると、初期状態は、「0番目に注目していて、合計が0」という状態になります。これを、(0, 0)とでも書きましょう。
状態(0, 0)から考えられる次の状態は、
(1) 0番目の数字を選ばずに、次に進む→次の状態は、(1, 0)
(2) 0番目の数字を選んで、次に進む→次の状態は、(1, a[0])
一般的には、状態(i, sum)の次の状態の候補は、
(1) i番目の数字を選ばない→(i + 1, sum)
(2) i番目の数字を選ぶ→(i + 1, sum + a)
となります。

深さ優先探索では、終端（i == nの状態ですね）に達するまで、進める方向にどんどん進んでいきます。（深さ優先探索と呼ばれる所以です。）
ここでは、(1)を再帰的に呼び出していく形になります。
終端状態に達した場合は、それが目的の状態かどうか調べます。今回の問題では、目的状態は(n, k)となります。
(1)を呼び出していった結果、(n, k)に到達しないとわかった場合、すなわちdfs関数がfalseを返した場合、
今度は、(2)を呼び出して、別の状態を探索します。

少し長くなりましたが、要は終端に達するまで深く潜っていき、終端に達したら、1つ戻って別の方向に潜っていく
ということを繰り返しながら、状態を全探索する方法になります。

[うしくん]

みなさん、説明ありがとうございます。
DFSについても説明は読んでいたのですが、理解不足でした。
DFSとこの表題の問題の関係についてだんだん理解が深まってきました。

[うしくん]

解決ってのを押しとくのを忘れてました。