[SWEA #12390] 배열2 - 부분집합의 합

문제

1부터 12까지의 숫자를 원소로 가진 집합 A가 있다. 집합 A의 부분 집합 중 N개의 원소를 갖고 있고, 원소의 합이 K인 부분집합의 개수를 출력하는 프로그램을 작성하시오.
해당하는 부분집합이 없는 경우 0을 출력한다. 모든 부분 집합을 만들어 답을 찾아도 된다.

예를 들어 N = 3, K = 6 경우, 부분집합은 { 1, 2, 3 } 경우 1가지가 존재한다.

 

입력

첫 줄에 테스트 케이스 개수 T가 주어진다.  ( 1 ≤ T ≤ 50 )

테스트 케이스 별로 부분집합 원소의 수 N과 부분 집합의 합 K가 여백을 두고 주어진다. ( 1 ≤ N ≤ 12, 1 ≤ K ≤ 100 )

 

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

내가 쓴 코드

'''
A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
'''
def subset(i, n, k):    # n : 원소 수, k : 원소 합
    global cnt
    if i == 12:  # 원소를 다 돌았을 때 : 1 ~ 12
        sum_subset = 0  # 원소 합 -> k
        num_subset = 0  # 원소 수 -> n
        for j in range(12):
            if bit[j]:
                sum_subset += A[j]
                num_subset += 1
                # if sum_subset > k:    # 더 효율적
                #     break
        if sum_subset == k:  # 원소 합이 k일 때
            if num_subset == n:
                cnt += 1
    else:
        bit[i] = 1  # i 포함
        subset(i + 1, n, k)
        bit[i] = 0  # i 미포함
        subset(i + 1, n, k)
    return cnt

T = int(input())
for t in range(T):
    N, K = map(int, input().split())
    A = [i for i in range(1, 13)]
    bit = [0] * 12
    cnt = 0         # 부분집합의 개수
    ans = subset(0, N, K)
    print(f'#{t+1} {ans}')

 

출력 결과

#1 1

#2 1

#3 0