[Baekjoon] #17610 - 양팔저울

상태 트리를 그릴 때 다음을 기준으로 가지를 뻗어나가면 된다.

추가 주어졌을 때 양팔 저울의 

• 좌측에 추를 올림
• 우측에 추를 올림
• 해당 추를 사용하지 않고 넘어감

ex) 좌측에 무게 1짜리 추를 올리고 우측에 무게 6짜리 추를 올리면 총 5라는 무게를 측정할 수 있다. 

 

def DFS(L, sum):
    global res
    if L == n:
        if 0 < sum <= s:
            res.add(sum)

    else:
        DFS(L + 1, sum + G[L])
        DFS(L + 1, sum - G[L])
        DFS(L + 1, sum)


if __name__ == "__main__":
    n = int(input())
    G = list(map(int, input().split()))
    s = sum(G)
    res = set()  # 측정될 수 있는 물의 무게 추가
    DFS(0, 0)
    print(s - len(res))