백준 1182번 : 부분수열의 합

[문제 링크] - https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

백트래킹 문제입니다.

 

한 가지 주의할 점이 있다면, 만약 부분수열의 누적합을 갖는 변수를 0으로 초기화하고, 만들어야 하는 정수가 0일 때 다음과 같이 로직을 작성할 수 있습니다.

def backtrack(idx, numberSum):
    global count
    if idx == N:
        return
    if numberSum == S:
        count += 1
    backtrack(idx + 1, numberSum + numberList[idx])
    backtrack(idx + 1, numberSum)

그러나 이렇게 하면 0으로 초기화한 numberSum과 S가 0일 때 항상 같다고 평가되므로, 둘을 평가하는 시점에서 초기값으로 비교하지 않도록 아래와 같이 코드를 작성해야 합니다.

def backtrack(idx, numberSum):
    global count
    if idx == N:
        return
        
    # 초깃값을 비교하는 것을 방지하기 위한 변수입니다.
    tempSum = numberSum + numberList[idx]
    if tempSum == S:
        count += 1
        
    backtrack(idx + 1, tempSum)
    backtrack(idx + 1, numberSum)

[정답 코드 - python]

N, S = map(int, input().split())
numberList = list(map(int, input().split()))
count = 0
tempList = []

def backtrack(idx, numberSum):
    global count
    if idx == N:
        return
    if numberSum == S:
        count += 1
    backtrack(idx + 1, numberSum + numberList[idx])
    backtrack(idx + 1, numberSum)

backtrack(0, 0)
print(count)