백준 / 실버 2 / 1182. 부분수열의 합

• 부분수열을 구하는 문제는, 결국엔 $N$개의 정수 중 일부를 선택해 조합을 만드는 것과 같음
• 수열에 $N$개의 정수가 있을 때, 인덱스 0부터 N-1에서 조합을 뽑아 이를 부분수열로 구성할 수 있음
• 단 부분수열 내 정수는 최대 $1$개, 최대 $N$개이므로, 조합 역시 $1$개를 뽑았을 때부터 $N$개를 뽑았을 때의 모든 경우를 고려해야 함

• 빈 수열부터 시작해, 매번 $0$ ~ $N - 1$ 중 숫자 하나를 선택함
  • 이때 원래 수열에서, 현재 조합의 마지막 수보다 큰 수만 뽑을 수 있음
• 아니면 지금까지 뽑은 수를 마지막으로 그만 뽑고, 종료할 수 있음
  • 단, 빈 부분수열은 만들 수 없으니, 맨 처음부터 종료할 순 없음
• 위 과정을 통해 $N$개의 수 중 $1$개, $2$개, ..., $N-1$개를 뽑은 조합을 모두 구할 수 있음

재귀를 이용한 풀이

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

# 현재 합이 curr인 부분수열에 원소를 추가한다
# 단 인덱스 i 이후 원소만 추가할 수 있다
def check_sum(i, curr):
    # 완성된 부분수열의 합이 S와 같은지 확인
    if i >= N:
        if curr == S:
            return 1
        else:
            return 0

    count = 0
    
    # 더 추가하는 경우
    for j in range(i, N):    
        count += check_sum(j + 1, curr + nums[j])
        
    # 더 추가 안 하고 멈추는 경우
    if i > 0:   # 아무것도 선택하지 않는 경우 제외
        count += check_sum(N, curr)
    
    return count 
    
# 현재 부분수열의 합은 0
# 0번째 인덱스 값부터 더할 수 있음
print(check_sum(0, 0))

• 위 아이디어를 코드로 구현하면 다음과 같음

재귀 조건

• check_sum(i, curr) 함수는, 현재 합이 curr인 상황에서 인덱스 i 이상의 새로운 수를 추가하려고 시도
  • 다음 숫자 j를 순회할 때, i 이상의 인덱스만 확인할 수 있게 함
  • 매번 숫자 j를 고를 때, check_sum(j + 1, curr + nums[j])로 호출하여 다음 재귀 호출에선 j + 1 이상의 인덱스만 고를 수 있게 구현
  • 추가로, i > 0(부분순열이 비어있지 않은 경우)일 땐 check_sum(N, curr + nums[j])를 뽑는 과정을 종료할 수 있음 (인덱스는 N-1까지만 있으므로)

종료 조건

• i >= N(부분순열의 모든 수를 뽑은 경우)이 된 경우
  • 현재 부분수열의 합과 S를 비교해 일치하면 1, 불일치하면 0을 반환
• check_sum 호출의 반환값을 계속 count 변수에 더해, 최종적으로 합이 S가 되는 부분수열의 수를 반환하게 함

시간 복잡도

• 순열의 길이가 $N$일 때, 총 만들 수 있는 부분수열의 수는 $2^N - 1$개
  • 각 숫자가 포함되었거나 포함되지 않음 -> 경우의 수는 $2$
  • 숫자가 총 $N$개이므로 $2^N$
  • 단 빈 순열은 제외해야 하므로 $2 ^ N - 1$
• $O(2^N)$, 하지만 $N \leq 20$이므로 최대 $1,048,576$번 -> 2초 안에 충분히 가능

기억할 점

• 순열 / 조합 문제를 재귀로 풀 땐, 직접 트리를 그려 스스로 생각한 논리가 맞는지 판단하고 코드를 친다.