[BaekJoon] 백준 1182번 부분수열의 합

[BaekJoon] 백준 1182번 부분수열의 합

 

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

 

내코드

 

문제를 봤을 때 N의 최대값이 100,000이었고 배열 전체를 다 돈다고 해도 시간초과가 나지 않을 것 같아서

백트래킹으로 풀어야 겠다고 생각했다.

dfs로 첫번째 숫자부터 탐색을 하면서 합이 S가 되면 결과값에 1을 더해줬다.

처음에는 이런 류의 문제가 어려웠는데 풀면서 익숙해지는 것 같다:)

 

# BaekJoon1182.py

N, S = map(int, input().split())
arr = list(map(int, input().split()))
visited = [False] * N
result = 0


# 방문하지 않은 처음은 제외하기 위해 사용
def check_false():
    global visited
    for i in range(N):
        if visited[i]:
            return True
    return False


def solve(summ, start):
    global result, N, S
    if summ == S and check_false():
        result += 1
    for i in range(start, N):
        if not visited[i]:
            visited[i] = True
            summ += arr[i]
            solve(summ, i)
            visited[i] = False
            summ -= arr[i]


solve(0, 0)
print(result)