配列内の要素の組み合わせを見つけるための再帰関数

Question

私はより大きなプログラミング上の問題を抱えています。まず、配列に目標値まで追加できる要素の組み合わせが含まれているかどうかを知る必要があります。

は

私が持っている機能は、次のヘッダーを持つことがあります。

bool sumCombination(const int a[], int size, int target); 

関数が再帰を使用しなければならない、とループのいずれかを使用してはならない、whileループまたはどこでもそれで単語「後藤」。さらに、ヘルパー関数を使用することはできません。

次のように機能する作品があるかのいくつかの例：

sumCombination([2, 4, 8], 3, 10) => true 
sumCombination([2, 4, 8], 3, 12) => true 
sumCombination([2, 4, 8], 3, 11) => false 
sumCombination([], 0, 0)   => true 

私は再帰を使用してこの問題に取り組むするかどうかはわかりませんし、私が働いている誰もがそれを行うことは不可能と思われる私に言っています与えられたパラメータ内で私はループを使ってこれを解決しました。しかし、私はループを使用せずに再帰でこれを完全に解決しようとしています。

誰でもこの問題の背後にある論理を理解する助けがあれば、とても感謝しています！

ありがとうございます！

Answer 1

bool sumCombination(const int a[], int size, int target) { 
    // Can always add up to zero. 
    if (!target) return true; 
    // No elements to add up to anything. 
    if (!size) return false; 
    return 
    // Try including the first element, see if tail adds up to the rest. 
    sumCombination(a + 1, size - 1, target - a[0]) || 
    // Finally, try the tail alone, without the first element. 
    sumCombination(a + 1, size - 1, target); 
} 

[非ゼロ目標和とサブセット和変異体（の