sum - 配列内の合計を見つけるためのアルゴリズム?

Question

すべて正で、数値 N より小さいことがわかっている要素を含む配列があるとします。

すべての要素の合計が正確に N になるサブセットが配列内にあるかどうかを調べるアルゴリズムの一般的で高レベルの説明を誰かが教えてくれませんか?

特に効率的である必要はありません。私が扱っているセットは非常に小さいです。

Answer 1

効率が重要でない場合、高レベルのアルゴリズムは次のとおりです。

input: array A[1..K] of positive numbers, positive N

    for each subset S of { 1..K }
        sum = 0
        for each i in S
            sum = sum + A[i]
        end
        if (sum equals N) return true
    end
    return false

Answer 2

擬似コード。非常に非効率的です。

if empty(numbers) return false
return hasSumSubset(numbers, N)

boolean hasSumSubset(numbers[], N):
   p = pop(numbers)
   if empty(numbers) return N == p
   return hasSumSubset(numbers, N-p) or hasSumSubset(numbers, N)

これを実際に実装する場合numbersは、再帰呼び出し用にコピーされていることを確認してください（refによって渡されないようにしてください）。そうしないと、正しく機能しません。