[파이썬 심화] 부분 수열의 합

부분 수열의 합

 

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


[입력]

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

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

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

def count_subsets_with_sum(numbers, target_sum):
    count = 0
    N = len(numbers)

    def backtrack(start_index, current_sum):
        nonlocal count

        if current_sum == target_sum:
            count += 1

        for i in range(start_index, N):
            if current_sum + numbers[i] <= target_sum:
                backtrack(i + 1, current_sum + numbers[i])

    backtrack(0, 0)
    return count

# 입력 처리
T = int(input("테스트 케이스의 수를 입력하세요: "))
for _ in range(T):
    N, K = map(int, input().split())
    numbers = list(map(int, input().split()))

    # 결과 출력
    result = count_subsets_with_sum(numbers, K)
    print("합이", K, "가 되는 경우의 수:", result)

 

1. count_subsets_with_sum(numbers, target_sum): 주어진 숫자 집합에서 부분집합을 구하여 그 합이 target_sum이 되는 경우의 수를 계산합니다.
   • numbers: 주어진 숫자 집합입니다.
   • target_sum: 목표 합계 값입니다.
   • 이 함수는 재귀적으로 백트래킹을 사용하여 가능한 모든 부분집합을 조사하고, 그 합이 target_sum과 일치하는 경우를 세어 반환합니다.
2. backtrack(start_index, current_sum): 재귀적으로 부분집합을 탐색하는 함수입니다.
   • start_index: 현재까지 고려된 숫자의 인덱스를 나타냅니다.
   • current_sum: 현재까지 선택된 숫자들의 합계를 나타냅니다.
3. 입력 처리 부분에서는 테스트 케이스의 수를 입력받고, 각 테스트 케이스에 대해 N, K, 그리고 숫자 집합을 입력받습니다.
4. 마지막으로 각 테스트 케이스마다 해당하는 합이 K가 되는 경우의 수를 출력합니다.