[Algorithm][Python] 백준(BOJ) 1182 부분 수열의 합 (Silver 2)

[문제]

https://www.acmicpc.net/problem/1182

---

풀이

항상 itertools의 combinations 라이브러리를 사용하여 풀어서, dfs를 이용하여 푸는 방법을 연습중이다.

[combinations 라이브러리 활용한 코드]

from itertools import combinations

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

for k in range(1, n+1):
    for x in combinations(nums, k):
        if sum(x) == s:
            result += 1

print(result)

[dfs(재귀) 를 활용한 코드]

def dfs(idx, sum):
    global result

    if idx >= n:
        return
    sum += nums[idx]
    if sum == s:
        result += 1

    dfs(idx+1, sum)
    dfs(idx+1, sum - nums[idx])

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

dfs(0,0)
print(result)

아래가 combinations 라이브러리를 이용한 방법, 위가 dfs를 활용한 방법이다.