[백준] 1182번: 부분수열의 합(Python, Backtracking)

1. 문제 링크

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

2. 풀이 

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

cnt = 0
def dfs(idx, sub_sum):
    global cnt

    if idx >= n:
        return

    sub_sum += array[idx]

    if sub_sum == s:
        cnt += 1

    dfs(idx + 1, sub_sum)
    dfs(idx + 1, sub_sum - array[idx])

    return

dfs(0, 0)

print(cnt)

 

3. 후기

백트래킹 문제 유형은 index의 값을 어떻게 넘기는지에 따라 조합, 순열 등 결과에 영향을 많이 받습니다.
대체로 문제에서 시키는 것대로 구현하는 느낌으로 Index를 활용하면 편할 것 같습니다.
ex. 다음으로 가야하므로 idx + 1, idx - 1

 

[코드 참조]

[출처: 부분 수열의 합 backtracking 코드]