1486. 장훈이의 높은 선반

#brute force
#
 
#탑의 높이는 점원이 1명일 경우 점원의 키
    # to_H = H[i]
# 2명 이상일 경우 탑을 만든 모든 점원의 키의 합
    # to_H = H[i] + ... + H[N-1]
#탑의 높이가 B이상인 경우 선반 위의 물건 사용 가능 단 높이가 b이상인 탑중 가장 낮은탑
    #if B < to_H :
    #   min(to_H)
import time
start = time.time()
 
 
def powerset(n, k, cursum):
    global ans
    #가지치기
    if ans < cursum : return #가지치기
 
 
 
    if n == k:
        # sum = 0
        # for i in range(N): # 부분집합의 원소의 합
        #     if bit[i] : sum += H[i]
        if cursum >= B: # 점원들의 키의 합이 선반보다는 커야한다.
            if ans > cursum: ans = cursum
 
    else:
        bit[k] = 1
        powerset(n, k+1, cursum + H[k])
        bit[k] = 0
        powerset(n, k+1, cursum)
 
T = int(input())
for tc in range(1, T+1):
    N, B = map(int, input().split()) # 점원수, 선반 높이
    H = list(map(int, input().split())) #점원들의 키
    bit = [0] * N
    ans = 987654321
    powerset(N, 0, 0)
    print("#{} {}".format(tc, ans- B))
 
print(time.time() - start)