Skip to main content
Back to problems
#3183
Medium Algorithms

The number of ways to make the sum

Array Dynamic Programming
51.1% acceptance
Mar 31, 2026
21
1
You have an infinite number of coins with values 1, 2, and 6, and only 2 coins with value 4. Given an integer n, return the number of ways to make the sum of n with the coins you have. Since the answer may be very large, return it modulo 109 + 7. Note that the order of the coins doesn't matter and [2, 2, 3] is the same as [2, 3, 2].

Solution

Rust
Time O(n²)
Space O(n)
LeetCode
solution.rs
impl Solution {
  pub fn number_of_ways(n: i32) -> i32 {
    let n = n as usize;
    let modp = 1_000_000_007i64;
    let mut dp = vec![0i64; n + 1];
    dp[0] = 1;
    for &coin in &[1, 2, 6] {
      for j in coin..=n {
        dp[j] = (dp[j] + dp[j - coin]) % modp;
      }
    }
    let mut ans = dp[n];
    if n >= 4 { ans = (ans + dp[n - 4]) % modp; }
    if n >= 8 { ans = (ans + dp[n - 8]) % modp; }
    ans as i32
  }
}