5260. [파이썬 SW 문제해결 최적화] 3일차 - 부분 집합의 합

이미 부분집합에 포함된 원소의 합들 S와 포함안된 원소의 합들 R을 이용하여 한계치를 만들어 쓸떼없는 계산을 줄이는 것이다.

위 그림에서 왼쪽으로 가면 포함, 오른쪽으로 가면 미포함이다.

S가 기준점 K를 넘을 경우, 그 트리부분은 진행하지 않는다. 뭘 더하든 K 이상이기 때문이다.

또 R가 기준점 K보다 작을 경우, 그 트리 부분은 진행하지 않는다. R은 전체원소의 합에서 후보원소에서 제외한 만큼 빼는 것으로, R을 넘는 S의 합이 나올 수가 없다.

앞으로 남아있는 모든 원소를 더해도 K는 되지 못할 것이므로..

import sys

sys.stdin = open("sample_input.txt", "r")

def allPartSum(i,K,S,R):
    global result
    if i == 0:
        if S == K:
            result += 1
        return
    if S > K: return
    if R < K: return
    allPartSum(i - 1, K, S + jiphap[i], R)
    allPartSum(i - 1, K, S,R - jiphap[i])


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N, K = map(int, input().split())
    jiphap = list(range(N+1))
    S = 0
    allsum = sum(jiphap)
    result = 0
    allPartSum(N,K,0,allsum)
    print("#{}".format(test_case),result)
    # ///////////////////////////////////////////////////////////////////////////////////