금액 경우의 수 계산하기

e.g) 1, 2, 5, 10, 20 ,50 만원으로 100만원을 계산하는 방법은 몇가지인가?

// 재귀
public class Main {
    
    public static void main(String[] args) {
        System.out.println(solution(new int[]{1, 2, 5, 10, 20, 50}, 100));
    }

    static int solution(int[] bills, int money) {
        return numOfPayAmount(money, bills, bills.length);
    }

    private static int numOfPayAmount(int money, int[] bills, int category) {
        int answer = 0;
        if (category == 1) {
            if (money % bills[0] == 0) {
                return 1;
            } else {
                return 0;
            }
        } else {
            int length = money / bills[category - 1];
            for (int i = 0; i <= length; i++) {
                int newMoney = money - (bills[category - 1] * i);
                answer += numOfPayAmount(newMoney, bills, category - 1);
            }
            return answer;

        }
    }

}

// 단순 포문