[백준][백트래킹] 1182. 부분수열의 합

1182. 부분수열의 합

 

• 내 풀이
  • 0 이 여러개인 경우 같은 부분수열이 나올 수 있음
  • 여러번 ans+1 하지 않도록 set에 담아 걸러내기

n, s = map(int, input().split())
nums = list(map(int, input().split()))
nums_set = ()

ans = 0

def comb(start, cnt, tmp):
    global ans
    if cnt >= 1:
        if tmp in nums_set:
            return
        if sum(tmp) == s:
            ans += 1
        if cnt == n:
            return

    for i in range(start, n):
        tmp.append(nums[i])
        comb(i+1, cnt+1, tmp)
        tmp.pop()


comb(0, 0, [])
print(ans)