❓문제 설명

---

• m 그램(gram)을 담을 수 있는 가방에 사탕을 가득 채우는 경우의 수를 구하려 합니다. 단, 같은 사탕은 또 넣을 수 없습니다.
• 가방이 감당할 수 있는 무게 m, 사탕별 무게가 담긴 배열 weights가 매개변수로 주어질 때, 가방을 정확히 m 그램으로 채우는 경우의 수를 return 하는 solution 함수를 작성해주세요.

❗제한 조건

---

• m은 1,000 이상 100,000 이하인 자연수입니다.
• 모든 사탕의 무게는 10 이상 100,000 이하인 자연수입니다.
• weights의 길이는 3 이상 15 이하입니다.

📌 풀이

---

1. 어떤 수를 담았을 때, 나머지 무게와 나머지 배열로 또 다시 solution 함수를 재귀적으로 호출해 구현

cnt = 0

def solution(m, weights):
    global cnt 
    if m == 0: 
        cnt += 1
    elif len(weights) == 1: 
        if m == weights[0]:
            cnt += 1
    else: 
        if m >= weights[0]:
            solution(m-weights[0], weights[1:])
        solution(m, weights[1:])
    return cnt