両腕秤アルゴリズム(DFS)

質問:

異なる重量のK個のテーパと空きボウルがあります.各ピボットの重量は整数で、器の重量は0です.
とみなす一度両腕秤で欲しい水の重さをボウルに盛り付けたいです.
与えられたすべての重量の和はSである.たとえば、ピボットあたり3個の重量を追加
面、S=9、両腕秤を1回使うだけで、1~Sの間のすべての重量に対応する水を
一緒にボウルに盛ることができます.Xはボウルに盛られた水の重さを表し、汚れたボウルも表します.
ピボット軸の重量が{1,5,7}の場合、S=13、ボウル中の水の重量が{1,2,3,4,5である.
6、7、8、11、12、13}は、1~Sの間に重量9~10の水を入れる、
できません.
K(3<=K<=13)個のピボット重量が与えられた場合、1~Sの間の整数における測定不可能な水の重量
何種類あるかを印刷するプログラムを作成してください.

説明の入力

第1行は自然数K(3<=K<=13)を与える.
2行目では、各Kピボットの重量はスペースの間にあります.各枢椎の重量は1から始まる.
200000までです.

入力例:

3
1 5 7

出力例:

2

textcode :

受信

入力

変数の割り当てと準備
s:すべてのボタンの合計
chk dup:1~sが利用可能かどうか.この値が0の場合に使用されます.
cnt:返すcnt値をsと指定
chk use:このボタンを使用するかどうか.初期初期化は0(未使用)です.

dfsを次の増分とし、以前に値が増加しなかった場合、cnt--

0(未使用)、1(左ボウルとともにアップロードされた値)2(右側の比較値)が使用可能かどうか
したがって、通常、ノードは0、1として使用され、未使用の3つの場合のみ区別される.

トラブルシューティング手順:

最初は秋の値をつけられるソートの問題だと思っていましたが、
(探した重量+2):6は同じ値を得ることができます.
したがって,現在より小さいテーパを減算するには,得られた値も加算する.

def get_all_sum(d, sum):
    global cnt
    if sum_arr[sum] != 0:
        sum_arr[sum] = 0
        cnt -= 1
    if d >= n:
        return
    get_all_sum(d+1, sum+coin[d]) 
    get_all_sum(d+1, sum)
    if sum - coin[d] > 0 :
        get_all_sum(d-1, sum-coin[d])

だから最後の2行を追加しましたが、ここにはありません.発見されました.
選択されていない理由を確認した結果、現在のデップの添加量は以前の値より大きいことがわかりました.
1,2,6があれば、1,2を1つの状態に加えて6と比較するので、今はボタンを外すことができません...
そこで質問を再確認しましたが、現在適用されていないケースは

これです...
これ以上やってはいけない.
だから私はすべてのノードの値をチェックすることにしました.

import sys

n = int(sys.stdin.readline())
coin = list(map(int, sys.stdin.readline().split()))
s = sum(coin)
chk_dup = [i for i in range(s + 1)]
# 중복방지
cnt = s
# 리턴할 값
chk_use = [0] * (len(coin))
# 사용여부 chk : 0 = 미사용, 1 왼쪽, 2, 오른쪽

def get_all_sum(d):
    global cnt
    if d >= n:
        temp = 0
        for i in reversed(range(n)):
            if chk_use[i] == 1:
                temp -= coin[i]
            elif chk_use[i] == 2:
                temp += coin[i]
        # print(temp, chk_use)
        if temp > 0 and chk_dup[temp] > 0: 
            #1보다 큰 경우에는 무게가 존재 + 중복방지
            chk_dup[temp] = 0
            cnt -= 1
        return
    chk_use[d] = 2
    get_all_sum(d+1) 
    chk_use[d] = 1
    get_all_sum(d+1)
    chk_use[d] = 0
    get_all_sum(d+1)

get_all_sum(0)
print(cnt)

重量/非繰返し値がある場合のみ、すべてのノードを確認します.
本当は降りたかったんだけど.
一時停止はきっとどこかで起こると思っていたが、起こらなかった.
秋衣の数が少ないかららしい…?
とりあえず完成~!