백준 1182 부분수열의 합

27.5m

틀린 답

import sys
import itertools

input = sys.stdin.readline
n, s = list(map(int, input().rstrip().split()))
nums = list(map(int, input().rstrip().split()))
pers = itertools.permutations(nums)
cnt = 0

for per in pers:
    if sum(per) == s:
        cnt += 1

print(cnt)

맞은 답

import sys
sys.setrecursionlimit(10 ** 4)

input = sys.stdin.readline
n, s = list(map(int, input().rstrip().split()))
nums = list(map(int, input().rstrip().split()))
cnt = 0

def back(res, idx):
    global cnt
    if idx >= n:
        return
    if res + nums[idx] == s:
        cnt += 1
    back(res + nums[idx], idx + 1)
    back(res, idx + 1)

back(0, 0)
print(cnt)

계속 틀리다 나중에서야 맞았는데,
이유는 계산 중간 값 res가 s랑 동일할 때 return을 해버려서였다...
아아아앙아ㅏㄱ 이런거 생각좀 잘 해야되는데!!!!!!!!!

고친 답

import sys
import itertools

input = sys.stdin.readline
n, s = list(map(int, input().rstrip().split()))
nums = list(map(int, input().rstrip().split()))
cnt = 0

for i in range(1, n + 1):
    combs = itertools.combinations(nums, i)
    for comb in combs:
        if sum(comb) == s:
            cnt += 1

print(cnt)

위에서 틀린 이유는 combinations가 아닌 permutations를 썼기 떄문이었다. 이렇게해도 정답은 된다. 근데 이제 문제가 의도한 풀이는 아니긴하다.