The Number of Ways to Make the Sum - Practice Coding Problems

The Number of Ways to Make the Sum - Problem

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 10⁹ + 7.

Note that the order of the coins doesn't matter and [2, 2, 3] is the same as [2, 3, 2].

Input & Output

Example 1 — Small Sum

$ Input: n = 8

› Output: 21

💡 Note: Multiple ways to make 8: using coins {1,1,6}, {2,2,2,2}, {1,1,2,4}, {4,4}, etc. Total of 21 different combinations.

Example 2 — Minimum Case

$ Input: n = 1

› Output: 1

💡 Note: Only one way to make sum 1: use a single coin of value 1.

Example 3 — Medium Sum

$ Input: n = 4

› Output: 5

💡 Note: Ways to make 4: {1,1,1,1}, {1,1,2}, {2,2}, {4}. Note we can use one coin-4 from our limited supply.

Constraints

1 ≤ n ≤ 10⁴
Answer modulo 10⁹ + 7

Visualization

Tap to expand

Understanding the Visualization

Available Coins

Unlimited: 1,2,6 coins. Limited: exactly 2 coins of value 4

State Tracking

Track (remaining_sum, coin4_used) to avoid overcounting

Combine Results

Sum all ways using 0, 1, or 2 coin-4s

Key Takeaway

🎯 Key Insight: Track limited coin usage as part of DP state to handle mixed constraints correctly

Asked in

G Google 25 a Amazon 20 M Microsoft 15

This is a coin change variation with mixed constraints. The key insight is to track the number of limited coin-4s used as part of the DP state. Best approach uses 2D DP with state (sum, coin4_count). Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(3ⁿ)	O(n)	Try all possible coin combinations recursively
Bottom-Up 2D DP	O(n)	O(n)	Build solution table iteratively from base cases
Memoization (Top-Down DP)	O(n)	O(n)	Cache recursive results to avoid recomputation

Recursive Brute Force — Algorithm Steps

Try using 0, 1, or 2 coins of value 4
For remaining sum, recursively try coins 1, 2, 6
Count all valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with target sum n

Branch

Try each coin type (1,2,6,4)

Recurse

Solve subproblems for remaining sum

Code -

solution.c — C

#include <stdio.h>

const int MOD = 1000000007;

int backtrack(int remaining, int coin4Used) {
    if (remaining == 0) return 1;
    if (remaining < 0) return 0;
    
    long long count = 0;
    // Try coin 1
    count += backtrack(remaining - 1, coin4Used);
    // Try coin 2
    count += backtrack(remaining - 2, coin4Used);
    // Try coin 6
    count += backtrack(remaining - 6, coin4Used);
    // Try coin 4 (if we haven't used 2 already)
    if (coin4Used < 2) {
        count += backtrack(remaining - 4, coin4Used + 1);
    }
    
    return count % MOD;
}

int solution(int n) {
    return backtrack(n, 0);
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3ⁿ)

Each recursive call branches into 3 choices (coins 1,2,6), depth up to n

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler