상품권 조합 세기

문제

지갑에 액면가가 적힌 상품권이 여러 장 들어 있습니다. cards[i]는 i번째 상품권의 액면가입니다.

계산대에서 상품권을 정확히 k장 내밀어 합계가 정확히 target이 되게 하려고 합니다. 가능한 조합이 몇 가지인지 반환하세요.

• 같은 상품권을 두 번 낼 수는 없습니다 (한 장은 한 번만 사용).
• 액면가가 같은 상품권이 여러 장 있을 수 있으며, 이들은 서로 다른 장으로 구분합니다. 예를 들어 [9,9,9]에서 2장을 고르는 방법은 3가지입니다.
• 내미는 순서는 구분하지 않습니다.

function solution(cards: number[], k: number, target: number): number

예시

제약 조건

• 1 ≤ cards.length ≤ 20
• 1 ≤ cards[i] ≤ 100
• 1 ≤ k ≤ 20 (cards.length보다 클 수 있습니다)
• 1 ≤ target ≤ 2,000

시간 복잡도 목표: O(2^N) 이내 — 가지치기를 곁들인 조합 탐색