python - 数値のリストから合計を作成できるかどうかを再帰的に確認する方法は?

Question

リストまたは数値のサブリストから合計を作成できるかどうかを再帰的に確認する方法は?

[23, 40, 20, 6, 3, 12, 20, 21, 18, 17]

list から 64 を作成できます[40,6,18]が、どのサブリストからも 34 を作成できません。

Answer 1

数値のリストまたはサブリストから合計を作成できるかどうかを判断するには:

1) 最初の番号から始めます。

2) その数が作成しようとしている合計と等しい場合は、停止してください。成功です。

3) その数が作成しようとしている合計よりも大きい場合は、次の数にスキップしてステップ 2 に進みます。

4) 求めている合計からその数を引きます。

5) このアルゴリズムを繰り返し、残りの数 (この後の数) で残りの合計を見つけようとします。

6) 次の番号に進みます。ない場合は停止します。

7) 手順 2 に進みます。

たとえば、[1, 13, 17, 8] から 55 の合計を見つけようとしている場合、次の 3 つの質問に減らすことができます。

1. [13, 17, 8] から 55-1 の合計を見つけることができますか? (これにより、最初の数字を含む解がすべて見つかります。)

2. [17, 8] から 55-13 の合計を見つけることができますか? (これにより、最初の数字が含まれていないが、2 番目の数字が含まれているソリューションが見つかります。)

3. [8] から 55-17 の合計を見つけることができますか? (これにより、1 番目または 2 番目の数値は含まないが、3 番目の数値は含むソリューションが検出されます。)

4. 解決策は8ですか？(これにより、最初の 3 つの数字は含まれないが、4 つ目の数字は含まれる解が見つかります。)

それぞれの新しい質問は、元の質問よりも用語が少ないことに注意してください。だからいつまでも続かない。

Answer 2

これが宿題である場合、再帰的でないソリューションを提供しても役に立ちません。宿題でない場合は、再帰を強制しないでください...代わりに itertools を使用してください。

>>> lst =[23, 40, 20, 6, 3, 12, 20, 21, 18, 17]
>>> from itertools import chain,combinations
>>> 
>>> def powerset(iterable):
...     "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
...     s = list(iterable)
...     return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
... 
>>> next(x for x in powerset(lst) if sum(x) == 64)
(23, 20, 21)