#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)
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
}
}