The Number of Ways to Make the Sum Solution in Python

Problem Description

Ah, the classic problem of making change! You know, like when you find yourself at a vending machine with a craving for snacks, but all you have is a crumpled dollar bill and a dream. The problem is simple: given a number n, how many ways can you make that sum using coins of denominations 1, 2, and 6?

Imagine you’re at a party, and you want to bring snacks. You can either bring 1 bag of chips, 2 bags of chips, or 6 bags of chips. But you want to know how many combinations of these bags you can bring to make exactly n bags. Spoiler alert: it’s not as easy as it sounds!

Code Solution

Copy Code

class Solution:
    def numberOfWays(self, n: int) -> int:
        kMod = 1_000_000_007
        dp = [1] + [0] * n

        for coin in (1, 2, 6):
            for i in range(coin, n + 1):
                dp[i] = (dp[i] + dp[i - coin]) % kMod

        ans = dp[n]
        if n - 4 >= 0:
            ans = (ans + dp[n - 4]) % kMod
        if n - 8 >= 0:
            ans = (ans + dp[n - 8]) % kMod
        return ans

Approach

The approach used in the code is dynamic programming. We maintain an array dp where dp[i] represents the number of ways to make the sum i using the available coin denominations. We initialize dp[0] to 1 because there’s one way to make the sum of 0: by using no coins at all. Then, for each coin, we iterate through the possible sums and update our dp array accordingly.

Time and Space Complexity

• Time Complexity: O(n * m), where n is the target sum and m is the number of coin denominations (which is constant in this case).
• Space Complexity: O(n), for the dp array.

Real-World Example

Let’s say you’re planning a movie night and you want to buy snacks. You can buy 1 bag of popcorn, 2 bags of chips, or 6 candy bars. If you want to spend exactly $n, how many combinations of these snacks can you buy? This problem is a perfect analogy for our coding challenge!