1182번 - 부분수열의 합

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

1182번: 부분수열의 합

이 문제는 백트래킹을 활용한 간단한 조합 문제이다.

그런데 '틀렸습니다' 가 떴다.

그때 작성한 코드는 아래와 같다.

# 부분수열의 합
import sys
input = sys.stdin.readline
# backtracking
def dfs(sum_value, idx):
    global answer
    if len(res) > 0 and sum_value == S:
        answer += 1
        return
        
    for i in range(idx, len(arr)):
        if visited[i] == False:
            visited[i] = True
            res.append(arr[i])
            dfs(sum(res), i+1)
            res.pop()
            visited[i] = False

N, S = map(int, input().split())
arr = list(map(int, input().split()))
visited = [False for _ in range(N)]
res = []
answer = 0

dfs(0, 0)

print(answer)

반례는 다음과 같다.

3 0

1 -1 0

 

만약 return을 해준다면 [1, -1] 일 때 함수가 return 해버리기 때문에 [1, -1, 0]은 고려하지 못한다.

따라서 [1, -1] 과 [0] 의 경우만을 answer에 저장한다. 

하지만 답은 [1, -1], [1, -1, 0], [0] 으로 총 answer에는 3이 저장되어야 한다.

따라서 아래처럼 수정하니 맞았다 :)

# 부분수열의 합
import sys
input = sys.stdin.readline
# backtracking
def dfs(sum_value, idx):
    global answer
    if len(res) > 0 and sum_value == S:
        answer += 1
        
    for i in range(idx, len(arr)):
        if visited[i] == False:
            visited[i] = True
            res.append(arr[i])
            dfs(sum(res), i+1)
            res.pop()
            visited[i] = False

N, S = map(int, input().split())
arr = list(map(int, input().split()))
visited = [False for _ in range(N)]
res = []
answer = 0

dfs(0, 0)

print(answer)