문제1216--CountSum 변형 - small

1216: CountSum 변형 - small

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

목표 정수 M(>=0)과 N개의 양의 정수가 주어집니다. 이들 정수를 최대 한 번만 사용하여 그것의 합이 목표 정수를 만들 수 있는 독특한 조합의 수를 알고 싶습니다.
예를 들어 목표 정수가 7이고, [5, 3, 4, 7]이 주어지면 (3, 4), (7) 총 2가지 독특한 조합의 수가 있습니다. 또 다른 예로 목표 정수가 2이고 [2, 5, 2, 1, 2]가 주어지면 (2, 2, 1), (2, 1, 2), (2, 1, 2), (5) 4가지가 있지만 (2, 2, 1), (2, 1, 2), (2, 1, 2)는 같은 조합이기 때문에 독특한 조합은 총 2가지 경우가 있습니다.

입력 설명

첫 줄에는 테스트케이스 T(1<=T<=10)가 주어집니다. 각 테스트케이스마다 첫 줄에는 목표 정수 M(0<=M<=19)과 N(2<=N<=5)이 주어집니다. 그다음 줄에는 N개의 양의 정수 X(1<=X<=19)가 주어집니다.

출력 설명

N개의 정수를 최대 한 번만 사용하여 그들의 합이 목표 정수가 되는 독특한 조합의 수를 출력해야 합니다.

입력 예시 Copy

2
7 4
5 3 4 7
5 5
2 5 2 1 2

출력 예시 Copy

2
2

출처/분류