Count ways to make change (DP)
Company: Walmart Labs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given an integer `amount` and an array of **positive, distinct** integers `coins`, where each coin value can be used **unlimited times**.
Return the number of **distinct combinations** of coins that sum to exactly `amount`.
Notes:
- The **order does not matter**. For example, `2+1` and `1+2` are the same combination.
- If `amount = 0`, there is exactly **one** way: choose no coins.
## Input/Output
- **Input:** integer `amount`, integer array `coins`
- **Output:** integer `ways`
## Examples
- `amount = 5, coins = [1,2,5]` → `4`
- Combinations: `5`, `2+2+1`, `2+1+1+1`, `1+1+1+1+1`
- `amount = 3, coins = [2]` → `0`
- `amount = 0, coins = [1,2]` → `1`
## Constraints (assume)
- `0 ≤ amount ≤ 10^4`
- `1 ≤ len(coins) ≤ 300`
- Result fits in 64-bit signed integer
Quick Answer: This question evaluates understanding of dynamic programming and combinatorial counting, focusing on unbounded coin usage and counting order‑independent combinations.
Return the number of order-insensitive combinations that sum to amount using unlimited copies of each coin.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (5, [1,2,5])
Expected Output: 4
Explanation: There are four order-insensitive combinations.
Input: (3, [2])
Expected Output: 0
Explanation: No combination reaches 3.
Input: (0, [1,2])
Expected Output: 1
Explanation: Choosing no coins is one way.
Input: (10, [10])
Expected Output: 1
Explanation: One coin can make the amount exactly.
Hints
- Clarify edge cases before coding.
- Keep outputs deterministic when several valid answers exist.