인쇄 동전 패턴

Question

는

가능한 중복 : 동전 패턴에서
Making change recursively: How do I modify my algorithm to print all combinations?

계산 문제 (값 N과 동전의 고정 세트를 감안할 때, 우리는 조합의 수를 계산해야 N까지 합칠 동전), 조합을 계산하는 조합을 인쇄하려면 접근 방법이 무엇입니까? 동적 프로그래밍을 사용해야합니까?

Answer 1

예, 필요합니다. amount_left까지 추가 coins [current_coin .. last_coin]의

print_combinations(amount_left, current_coin): 
    if amount_left == 0: 
     print "\n" 
     return 
    if current_coin == num_coins: 
     return 
    if dp[amount_left - coins[current_coin]] > 0: 
     print coins[current_coin], " " 
     print_combinations(amount_left - coins[current_coin], current_coin) 
    print_combinations(amount_left, current_coin + 1) 

이 기능은 인쇄의 모든 조합 : 다음 의사 코드 인쇄를 한 후 i 모든 조합을 추가 조합의 수는 dp[i]를 일치 한 가정. 따라서 동적 프로그래밍 테이블 dp[]이 표시되면 현재 동전을 사용하여 재발행 여부를 결정할 수 있습니다 (최소한 하나의 조합에과 같은 새로운 금액이 합산되는 경우에만 재귀됩니다).