Day 6 - Python

on

Problem Statement - Coin Change

You are given a set of coin denominations and a target amount. Determine the number of distinct combinations of coins that sum up to the target amount. You can assume an infinite supply of coins of each denomination.

Write a function count_combinations(coins, amount) that takes in two parameters:

coins: an array of positive integers representing the denominations of coins available.

amount: a positive integer representing the target amount.

The function should return an integer representing the number of distinct combinations of coins that sum up to the target amount.

Input Format

The first line contains an integer, n, the number of coin denominations.

The second line contains n space-separated integers representing the coin denominations.

The third line contains an integer, amount, the target amount.

Constraints

1 <= n <= 50

1 <= coin denomination <= 20 --> possible values [1, 2, 5, 10, 20]

1 <= amount <= 25

Output Format

Output a single integer representing the number of distinct combinations of coins that sum up to the target amount, followed by each combination printed on a new line.

Sample Input

3

1 2 5

12

Sample Output

13

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 2, 2]

[1, 1, 1, 1, 1, 1, 1, 5]

[1, 1, 2, 2, 2, 2, 2, 1, 1]

[1, 1, 2, 2, 2, 2, 2, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 5]

[1, 1, 1, 1, 1, 1, 1, 2, 2, 2]

[1, 1, 1, 1, 1, 5, 2, 2]

[1, 1, 1, 1, 2, 2, 2, 2, 2]

[1, 1, 1, 1, 2, 2, 2, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 2, 5]

Explanation

For the given denominations [1, 2, 5] and target amount 12, there are 13 distinct combinations of coins that sum up to 12. These combinations are listed as arrays, each representing a combination. The total number of combinations, 13, is printed first, followed by each combination on a new line.

Test Case 1:

Input

4

1 2 10 20

10

Output

7

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[1, 1, 1, 1, 1, 1, 1, 1, 2]

[1, 1, 1, 1, 1, 1, 2, 2]

[1, 1, 1, 1, 2, 2, 2]

[1, 1, 2, 2, 2, 2]

[2, 2, 2, 2, 2]

[10]

Input

5

1 2 5 10 20

25

Output

68

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2]

[1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2]

[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

[1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 5]

[1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 5]

[1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 5]

[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5]

[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 5, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 5, 5]

[1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 5, 5]

[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 5, 5]

[1, 1, 1, 2, 2, 2, 2, 2, 2, 5, 5]

[1, 2, 2, 2, 2, 2, 2, 2, 5, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 5, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 5, 5]

[1, 1, 1, 1, 1, 1, 2, 2, 5, 5, 5]

[1, 1, 1, 1, 2, 2, 2, 5, 5, 5]

[1, 1, 2, 2, 2, 2, 5, 5, 5]

[2, 2, 2, 2, 2, 5, 5, 5]

[1, 1, 1, 1, 1, 5, 5, 5, 5]

[1, 1, 1, 2, 5, 5, 5, 5]

[1, 2, 2, 5, 5, 5, 5]

[5, 5, 5, 5, 5]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 10]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 10]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 10]

[1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 10]

[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 10]

[1, 1, 1, 2, 2, 2, 2, 2, 2, 10]

[1, 2, 2, 2, 2, 2, 2, 2, 10]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 10]

[1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 10]

[1, 1, 1, 1, 1, 1, 2, 2, 5, 10]

[1, 1, 1, 1, 2, 2, 2, 5, 10]

[1, 1, 2, 2, 2, 2, 5, 10]

[2, 2, 2, 2, 2, 5, 10]

[1, 1, 1, 1, 1, 5, 5, 10]

[1, 1, 1, 2, 5, 5, 10]

[1, 2, 2, 5, 5, 10]

[5, 5, 5, 10]

[1, 1, 1, 1, 1, 10, 10]

[1, 1, 1, 2, 10, 10]

[1, 2, 2, 10, 10]

[5, 10, 10]

[1, 1, 1, 1, 1, 20]

[1, 1, 1, 2, 20]

[1, 2, 2, 20]

[5, 20]

SOLUTION

def find_combinations(coins, n, amount):

    dp = [[] for _ in range(amount + 1)]

    dp[0] = [[]]  


    for coin in coins:

        for j in range(coin, amount + 1):

            for combination in dp[j - coin]:

                dp[j].append(combination + [coin])


    return dp[amount]


def count_combinations(coins, amount):

    combinations = find_combinations(coins, len(coins), amount)

    print(len(combinations))

    for combination in combinations:

        print(combination)


n = int(input().strip())

coins = list(map(int, input().strip().split()))

amount = int(input().strip())


count_combinations(coins, amount)


Insights:

  • The program utilizes dynamic programming to solve the coin change problem efficiently. It employs memoization to avoid recomputing solutions for the same subproblems.
  • The find_combinations function iterates through each coin denomination and computes all possible combinations of coins that sum up to the target amount.
  • The dp array is used for memoization. It stores lists of combinations for each amount from 0 to the target amount. This helps avoid redundant calculations by storing and reusing intermediate results.
  • The count_combinations function prints the total number of combinations found and then prints each combination on a new line.
  • While the program is efficient for relatively small target amounts and coin denominations, it may become less practical for larger values. For scalability, further optimization or alternative algorithms may be needed.
  • dp[0] = [[]]: This line sets the initial value of dp[0] to a list containing an empty list []. This represents the base case where there is one way to make change for amount 0, which is an empty combination.
  • The nested loop structure iteratively constructs combinations of coins for each amount from the value of the current coin denomination up to the target amount, appending the newly formed combinations to the respective positions in the dp array.
Explore Dynamic Programming! An interesting concept! 
Happy Coding! :)

Comments

Post a Comment