[SWEA] 2817 : 부분 수열의 합 - Python

문제

A1, A2, ... , AN의 N개의 자연수가 주어졌을 때, 최소 1개 이상의 수를 선택하여 그 합이 K가 되는 경우의 수를 구하는 프로그램을 작성하시오.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 2개의 자연수 N(1 ≤ N ≤ 20)과 K(1 ≤ K ≤ 1000)가 주어진다.

두 번째 줄에는 N개의 자연수 수열 A가 주어진다. 수열의 원소인 N개의 자연수는 공백을 사이에 두고 주어지며, 1 이상 100 이하임이 보장된다.

[출력]

각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 부분 수열의 합이 K가 되는 경우의 수를 출력한다.

def dfs(L,sum):
    global cnt
    if sum > k:
        return # 가지치기
    if L == n: # 모두 확인. 종료조건
        if sum == k:
            cnt += 1
    else:
        dfs(L+1, sum + data[L]) # 현재 숫자 선택
        dfs(L+1, sum)


T = int(input())
for i in range(1,T+1):
    n,k = map(int, input().split())
    data = list(map(int, input().split())) # n 개
    cnt = 0
    dfs(0,0)
    print(f"#{i} {cnt}")

😓 코멘트

전형적인 백트랙킹(dfs) 문제. 현재 숫자가 속하는지, 안 속하는지를 계산해야함.

import itertools를 통해 itertools.combinations(data,k) 이런 식으로 모든 조합을 확인해도 되지만, 터질꺼야. 그러니까 해당 코드 알아놓기.

물론 재귀는 시간 복잡도 O(N*2^N)이다. 범위를 보고 잘 판단하면 돼