[백준/python]1182번 부분수열의 합 - backtracking

N과 M 문제보다 먼저 풀었다. 백트래킹에 대한 개념을 몰라서 백트래킹 문제 중에서도 상대적으로 쉬운 문제였지만 시간이 꽤 걸렸다. 첫 풀이도 백트래킹이지만 다른 사람들의 코드를 참고하여 더 간단하게 풀 수 있음을 알게 되었다.

코드

DFS를 이용해 재귀로 풀었다.

N, S = map(int, input().split())
arr = list(map(int, input().split()))

ans = 0
def DFS(visited, index):    

    global ans
    
    tmp=0
    for j in range(N):
        if visited[j]==1:
            tmp+=arr[j]
    
    if tmp==S:
        ans+=1
    
    
    for i in range(index, N):
        if visited[i]==0:
            visited[i]=1
            DFS(visited, i)
            visited[i]=0
            
    return
    
start = [0 for _ in range(N)]

for i in range(N):
    start[i]=1
    DFS(start,i) 
    start[i]=0

print(ans)

DFS( visited, index ) : visited 배열 내부에 방문한 곳을 체크한다. 이 때 i번째 인덱스가 마지막으로 선택된 인덱스이다. 재귀함수를 통해 현재 인덱스를 선택하고 DFS를 실행하고 다시 방문 상태를 되돌려 놓는다. 루프를 통해 방문 배열의 마지막 인덱스까지 실행한다.

재귀함수를 실행할 때마다 현재 표시된 인덱스들과 동일하게 부분수열을 뽑고 이 때 합이 S라면 전역 변수 ans에 1을 더해준다.

DFS를 1개만 뽑은 모든 경우에서 실행한다.

백트래킹

백트래킹 개념과 다른 사람들의 풀이를 참고했다.

N, S = map(int, input().split())
arr = list(map(int, input().split()))
tmp=0
sol = 0
def DFS(index):
    global tmp, sol
    if index == N :
        return

    if tmp + arr[index] == S:
        sol +=1

    DFS(index+1)
    
    tmp += arr[index]
    DFS(index+1)
    
    tmp -= arr[index] # 백트래킹

DFS(0)
print(sol)

처음에 푼 방식과 다르게 방문표시를 기준으로 DFS를 실행하고 다시 방문표시를 돌리지 않고 아예 부분 수열의 합을 기준으로 생각한다.

현재 인덱스를 선택한 경우 현재까지의 부분합에 현재 인덱스에 해당되는 수열 값을 더하고 DFS를 실행한 뒤 처음 상태로 되돌려 준다.

현재 인덱스를 선택하지 않은 경우 인덱스만 +1을 하고 DFS를 실행한다.

Ex) [1,2,3,4] 에서 합 6인 부분수열 찾기 (1-index)

tmp=0, DFS(1) 실행1

tmp=0, DFS(2) 실행2

tmp=1, DFS(2) 실행

tmp=0, DFS(3) 실행3

tmp=2, DFS(3) 실행14 →

tmp2, DFS(4) 실행 15 → tmp2, DFS(5) 실행16 return5(실행17) / tmp6, DFS(5) 실행18 return6(실행19)

tmp5, DFS(4) 실행 20 → …

tmp=0, DFS(4) 실행4,

tmp=3, DFS(4) 실행9 →

tmp=3, DFS(5) 실행10, return3(실행 11) / tmp=7, DFS(5) 실행12, return4(실행13)

tmp=0, DFS(5) 실행5 → return1(실행6)

tmp=4, DFS(5) 실행7 → return2(실행8)

네..이런식으로 재귀를 타고 올라갈 수 있다. 이렇게 푸는 방법을 혼자 생각하려면 아마 하루는 넘게 걸렸을 것 같다.