def sub_set(set_idx, num_sum, num_remain_sum):
global result
if set_idx == N:
if num_sum >= H:
result = min(result, num_sum - H)
return
if num_sum + num_remain_sum < H:
return
sub_set(set_idx + 1, num_sum + HEIGHTS[set_idx], num_remain_sum - HEIGHTS[set_idx])
sub_set(set_idx + 1, num_sum, num_remain_sum - HEIGHTS[set_idx])
T = int(input())
for tc in range(1, T + 1):
N, H = map(int, input().split())
HEIGHTS = list(map(int, input().split()))
result = 100000
sub_set(0, 0, sum(HEIGHTS))
print(f"#{tc} {result}")
부분집합을 구하지 않고, 진행하며 처리할 수 있는 방법도 생각해보기
중복된 연산을 하지 않도록 가지치기하는 방법에 대한 고민
# 남은 수를 더하더라도, 기준 값을 넘기지 못한다면 더이상 연산을 수행할 필요가 없다.
if num_sum + num_remain_sum < H:
return