문제 출처 : [SWEA] 4837 부분집합의 합
learn -> course -> programming intermediate -> list2 -> 부분집합의 합

문제

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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

코드

T = int(input())
for tc in range(1, T + 1):
    N, k = map(int, input().split())    # N : 부분집합의 원소 수 k : 부분집합 원소의 합
    num_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
    result_list = []        # 부분집합을 저장할 리스트

    # 비트 연산을 통해 모든 부분집합을 2차원 리스트 형태로 저장
    for i in range(1 << len(num_list)):     # 모든 부분집합의 개수
        sub_list = []       # 부분집합을 저장할 리스트
        for j in range(len(num_list)):      # 원소의 수만큼 비트를 비교
            if i & (1 << j):        # i번의 j번 비트가 1인 경우
                sub_list.append(num_list[j])
        result_list.append(sub_list)

    cnt = 0     # 부분집합 원소의 수가 N개 이면서 N개의 합이 k인 경우를 셀 변수 초기화
    # 부분집합의 수만큼 반복
    for i in range(len(result_list)):
        sum_num = 0     # 부분집합의 합을 구할 변수 초기화
        if len(result_list[i]) == N:    # 부분집합의 길이가 N일 경우
            for j in range(N):
                sum_num += result_list[i][j]    # 해당 부분집합의 합을 구함
            if sum_num == k:        # 그 합이 k일 경우
                cnt += 1        # cnt 변수에 + 1

    print('#{} {}'.format(tc, cnt))

풀이 방법

모든 부분집합을 만들기 위해서 비트 연산을 사용했다. 우선 모든 부분집합을 만들어서 2차원 리스트에 저장해두고 2차원 리스트를 순회하면서 문제의 조건에 맞는 부분집합들의 개수를 세서 출력해주었다.