Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogle

Number of Ways to Make Change

Choose your preparation mode4 modes available
🎯
Number of Ways to Make Change
mediumDPAmazonGoogle

Imagine you have an unlimited supply of coins of different denominations, and you want to find out how many distinct ways you can make a certain amount of money. This problem models that real-world scenario.

💡 This problem is a classic example of dynamic programming where beginners often struggle to understand why greedy approaches fail and how to count combinations rather than just check feasibility. It requires careful thinking about overlapping subproblems and how to build solutions incrementally.
📋
Problem Statement

Given an integer amount and a list of coin denominations, return the number of distinct ways to make up that amount using any number of coins. You can use each coin denomination an unlimited number of times. The order of coins does not matter.

1 ≤ amount ≤ 10^51 ≤ number of coin denominations ≤ 1001 ≤ coin denomination value ≤ amount
💡
Example
Input"amount = 5, coins = [1, 2, 5]"
Output4

The four ways are: 5=5; 5=2+2+1; 5=2+1+1+1; 5=1+1+1+1+1

  • amount = 0, coins = [1,2,3] → 1 (empty combination)
  • amount = 3, coins = [] → 0 (no coins to use)
  • amount = 7, coins = [2,4] → 0 (no combination sums to 7)
  • amount = 1, coins = [2,3,5] → 0 (coins larger than amount)
🔁
Why DP?
Why greedy fails:

Greedy fails because choosing the largest coin first does not guarantee all combinations are counted. For example, amount=5 with coins=[1,2,5]: greedy picks 5 once, but misses combinations like 2+2+1.

DP state:

dp[i][w] = number of ways to make amount w using the first i coin denominations.

Recurrence:dp[i][w] = dp[i-1][w] + dp[i][w - coins[i-1]] if w >= coins[i-1], else dp[i-1][w]

The number of ways to make amount w using first i coins equals ways without using the ith coin plus ways using at least one ith coin.

⚠️
Common Mistakes
Using greedy approach

Misses valid combinations, returns incorrect count

✅ Use DP to count all combinations

Not handling base case amount=0 correctly

Returns 0 instead of 1, missing empty combination

✅ Initialize dp[0] = 1 or return 1 when amount=0 in recursion

Counting permutations instead of combinations

Overcounts ways, giving wrong results

✅ Iterate coins outer loop, amounts inner loop to count combinations

Using 1D dp but iterating amounts backwards

Misses some combinations or counts duplicates

✅ Iterate amounts forward when coins are unlimited

Not memoizing in top-down approach

Exponential time, TLE

✅ Add memo dictionary or map to cache results

🧠
Brute Force (Pure Recursion)
💡 Starting with brute force helps understand the problem's recursive structure and why naive solutions are inefficient.

Intuition

Try all combinations by either including or excluding each coin for the current amount recursively.

Algorithm

  1. If amount is 0, return 1 as a valid combination is found.
  2. If amount is negative or no coins left, return 0 as no valid combination.
  3. Recursively count ways by including the current coin and excluding it.
  4. Sum both counts to get total ways.
💡 The recursion explores all subsets, which is conceptually simple but computationally expensive.
Recurrence:ways(i, amount) = ways(i-1, amount) + ways(i, amount - coins[i])
</>
Code
def count_ways(coins, n, amount):
    if amount == 0:
        return 1
    if amount < 0 or n == 0:
        return 0
    return count_ways(coins, n - 1, amount) + count_ways(coins, n, amount - coins[n - 1])

# Driver code
coins = [1, 2, 5]
amount = 5
print(count_ways(coins, len(coins), amount))
Line Notes
if amount == 0:Base case: exact amount formed means one valid way
if amount < 0 or n == 0:No valid way if amount negative or no coins left
return count_ways(coins, n - 1, amount)Exclude current coin and recurse
return count_ways(coins, n, amount - coins[n - 1])Include current coin and recurse
public class Solution {
    public static int countWays(int[] coins, int n, int amount) {
        if (amount == 0) return 1;
        if (amount < 0 || n == 0) return 0;
        return countWays(coins, n - 1, amount) + countWays(coins, n, amount - coins[n - 1]);
    }
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        System.out.println(countWays(coins, coins.length, amount));
    }
}
Line Notes
if (amount == 0) return 1;Base case: found a valid combination
if (amount < 0 || n == 0) return 0;No valid combination if amount negative or no coins
return countWays(coins, n - 1, amount)Exclude current coin and recurse
return countWays(coins, n, amount - coins[n - 1])Include current coin and recurse
#include <iostream>
using namespace std;

int countWays(int coins[], int n, int amount) {
    if (amount == 0) return 1;
    if (amount < 0 || n == 0) return 0;
    return countWays(coins, n - 1, amount) + countWays(coins, n, amount - coins[n - 1]);
}

int main() {
    int coins[] = {1, 2, 5};
    int amount = 5;
    int n = sizeof(coins) / sizeof(coins[0]);
    cout << countWays(coins, n, amount) << endl;
    return 0;
}
Line Notes
if (amount == 0) return 1;Base case: valid combination found
if (amount < 0 || n == 0) return 0;No valid combination if amount negative or no coins
return countWays(coins, n - 1, amount)Exclude current coin and recurse
return countWays(coins, n, amount - coins[n - 1])Include current coin and recurse
function countWays(coins, n, amount) {
    if (amount === 0) return 1;
    if (amount < 0 || n === 0) return 0;
    return countWays(coins, n - 1, amount) + countWays(coins, n, amount - coins[n - 1]);
}

const coins = [1, 2, 5];
const amount = 5;
console.log(countWays(coins, coins.length, amount));
Line Notes
if (amount === 0) return 1;Base case: found a valid way
if (amount < 0 || n === 0) return 0;No valid way if amount negative or no coins
return countWays(coins, n - 1, amount)Exclude current coin and recurse
return countWays(coins, n, amount - coins[n - 1])Include current coin and recurse
⏱
Complexity
TimeO(2^n) exponential due to exploring all subsets
SpaceO(n) recursion stack depth

Each call branches into two, leading to exponential calls; stack depth is at most number of coins.

💡 For n=20 coins, this means over a million calls, which is impractical.
Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠
Top-Down Memoization
💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving efficiency.

Intuition

Store results of recursive calls in a table keyed by coin index and amount to reuse them.

Algorithm

  1. Initialize a memo table to store results for each (coin index, amount).
  2. If amount is 0, return 1.
  3. If amount < 0 or no coins left, return 0.
  4. If result in memo, return it to avoid recomputation.
  5. Otherwise, compute ways by excluding and including current coin, store in memo.
💡 Memoization converts exponential recursion into polynomial time by caching.
Recurrence:ways(i, amount) = ways(i-1, amount) + ways(i, amount - coins[i])
</>
Code
def count_ways_memo(coins, n, amount, memo=None):
    if memo is None:
        memo = {}
    if amount == 0:
        return 1
    if amount < 0 or n == 0:
        return 0
    if (n, amount) in memo:
        return memo[(n, amount)]
    memo[(n, amount)] = count_ways_memo(coins, n - 1, amount, memo) + count_ways_memo(coins, n, amount - coins[n - 1], memo)
    return memo[(n, amount)]

# Driver code
coins = [1, 2, 5]
amount = 5
print(count_ways_memo(coins, len(coins), amount))
Line Notes
memo = {}Initialize memo dictionary to cache results
if (n, amount) in memo:Check if result already computed to avoid recomputation
memo[(n, amount)] = ...Store computed result in memo
return memo[(n, amount)]Return cached or newly computed result
import java.util.HashMap;
import java.util.Map;

public class Solution {
    static Map<String, Integer> memo = new HashMap<>();
    public static int countWaysMemo(int[] coins, int n, int amount) {
        if (amount == 0) return 1;
        if (amount < 0 || n == 0) return 0;
        String key = n + "," + amount;
        if (memo.containsKey(key)) return memo.get(key);
        int res = countWaysMemo(coins, n - 1, amount) + countWaysMemo(coins, n, amount - coins[n - 1]);
        memo.put(key, res);
        return res;
    }
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        System.out.println(countWaysMemo(coins, coins.length, amount));
    }
}
Line Notes
static Map<String, Integer> memoMemo map to cache results keyed by coin index and amount
if (memo.containsKey(key))Return cached result if available
memo.put(key, res);Store computed result in memo
return res;Return computed or cached result
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

unordered_map<string, int> memo;

int countWaysMemo(int coins[], int n, int amount) {
    if (amount == 0) return 1;
    if (amount < 0 || n == 0) return 0;
    string key = to_string(n) + "," + to_string(amount);
    if (memo.find(key) != memo.end()) return memo[key];
    memo[key] = countWaysMemo(coins, n - 1, amount) + countWaysMemo(coins, n, amount - coins[n - 1]);
    return memo[key];
}

int main() {
    int coins[] = {1, 2, 5};
    int amount = 5;
    int n = sizeof(coins) / sizeof(coins[0]);
    cout << countWaysMemo(coins, n, amount) << endl;
    return 0;
}
Line Notes
unordered_map<string, int> memo;Memo map to cache results
if (memo.find(key) != memo.end())Return cached result if found
memo[key] = ...Store computed result in memo
return memo[key];Return cached or computed result
const memo = new Map();
function countWaysMemo(coins, n, amount) {
    if (amount === 0) return 1;
    if (amount < 0 || n === 0) return 0;
    const key = n + ',' + amount;
    if (memo.has(key)) return memo.get(key);
    const res = countWaysMemo(coins, n - 1, amount) + countWaysMemo(coins, n, amount - coins[n - 1]);
    memo.set(key, res);
    return res;
}

const coins = [1, 2, 5];
const amount = 5;
console.log(countWaysMemo(coins, coins.length, amount));
Line Notes
const memo = new Map();Memo map to cache results
if (memo.has(key))Return cached result if available
memo.set(key, res);Store computed result in memo
return res;Return cached or computed result
⏱
Complexity
TimeO(n * amount) due to memoization caching each state once
SpaceO(n * amount) for memo table and recursion stack

Memoization ensures each (coin index, amount) pair is computed once.

💡 For amount=1000 and 10 coins, this means about 10,000 computations, which is efficient.
Interview Verdict: Accepted

Memoization is a practical optimization that makes the solution efficient enough for interviews.

🧠
Bottom-Up Tabulation
💡 Tabulation builds the solution iteratively from smaller subproblems, which is often easier to debug and understand than recursion.

Intuition

Use a 2D dp table where dp[i][w] stores ways to make amount w using first i coins, filling it row by row.

Algorithm

  1. Initialize dp table with dp[0][0] = 1 (0 amount with 0 coins).
  2. Iterate over coins and amounts, filling dp[i][w].
  3. For each cell, add ways excluding current coin (dp[i-1][w]) and including it (dp[i][w - coin]).
  4. Return dp[n][amount] as final answer.
💡 Tabulation explicitly shows how solutions build up from base cases.
Recurrence:dp[i][w] = dp[i-1][w] + dp[i][w - coins[i-1]] if w >= coins[i-1], else dp[i-1][w]
</>
Code
def count_ways_tab(coins, amount):
    n = len(coins)
    dp = [[0] * (amount + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1
    for i in range(1, n + 1):
        for w in range(amount + 1):
            dp[i][w] = dp[i - 1][w]
            if w >= coins[i - 1]:
                dp[i][w] += dp[i][w - coins[i - 1]]
    return dp[n][amount]

# Driver code
coins = [1, 2, 5]
amount = 5
print(count_ways_tab(coins, amount))
Line Notes
dp = [[0] * (amount + 1) for _ in range(n + 1)]Create dp table with rows for coins and columns for amounts
for i in range(n + 1): dp[i][0] = 1Base case: one way to make amount 0 (empty set)
dp[i][w] = dp[i - 1][w]Ways excluding current coin
dp[i][w] += dp[i][w - coins[i - 1]]Add ways including current coin if possible
public class Solution {
    public static int countWaysTab(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= amount; w++) {
                dp[i][w] = dp[i - 1][w];
                if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];
            }
        }
        return dp[n][amount];
    }
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        System.out.println(countWaysTab(coins, amount));
    }
}
Line Notes
int[][] dp = new int[n + 1][amount + 1];Initialize dp table for coins and amounts
for (int i = 0; i <= n; i++) dp[i][0] = 1;Base case: one way to make amount 0
dp[i][w] = dp[i - 1][w];Ways excluding current coin
if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];Add ways including current coin
#include <iostream>
#include <vector>
using namespace std;

int countWaysTab(vector<int>& coins, int amount) {
    int n = coins.size();
    vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
    for (int i = 0; i <= n; i++) dp[i][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= amount; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];
        }
    }
    return dp[n][amount];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amount = 5;
    cout << countWaysTab(coins, amount) << endl;
    return 0;
}
Line Notes
vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));Create 2D dp table initialized to 0
for (int i = 0; i <= n; i++) dp[i][0] = 1;Base case: one way to make amount 0
dp[i][w] = dp[i - 1][w];Ways excluding current coin
if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];Add ways including current coin
function countWaysTab(coins, amount) {
    const n = coins.length;
    const dp = Array.from({ length: n + 1 }, () => Array(amount + 1).fill(0));
    for (let i = 0; i <= n; i++) dp[i][0] = 1;
    for (let i = 1; i <= n; i++) {
        for (let w = 0; w <= amount; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];
        }
    }
    return dp[n][amount];
}

const coins = [1, 2, 5];
const amount = 5;
console.log(countWaysTab(coins, amount));
Line Notes
const dp = Array.from({ length: n + 1 }, () => Array(amount + 1).fill(0));Initialize 2D dp array
for (let i = 0; i <= n; i++) dp[i][0] = 1;Base case: one way to make amount 0
dp[i][w] = dp[i - 1][w];Ways excluding current coin
if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];Add ways including current coin
⏱
Complexity
TimeO(n * amount) iterating over coins and amounts
SpaceO(n * amount) for dp table

Each dp cell computed once using previously computed cells.

💡 For amount=1000 and 10 coins, about 10,000 operations, efficient for interviews.
Interview Verdict: Accepted

Tabulation is a preferred approach for clarity and iterative control.

🧠
Space Optimized Bottom-Up (1D DP)
💡 We can reduce space by using a 1D dp array since current row depends only on current and previous states in a specific order.

Intuition

Use a single array where dp[w] represents ways to make amount w, updating it as we iterate over coins.

Algorithm

  1. Initialize dp array of size amount+1 with dp[0] = 1.
  2. For each coin, iterate amounts from coin value to amount.
  3. Update dp[w] by adding dp[w - coin] to count ways including current coin.
  4. Return dp[amount] as final answer.
💡 This approach uses forward iteration to avoid counting duplicates and saves space.
Recurrence:dp[w] += dp[w - coin]
</>
Code
def count_ways_space_opt(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for w in range(coin, amount + 1):
            dp[w] += dp[w - coin]
    return dp[amount]

# Driver code
coins = [1, 2, 5]
amount = 5
print(count_ways_space_opt(coins, amount))
Line Notes
dp = [0] * (amount + 1)Initialize 1D dp array for amounts
dp[0] = 1Base case: one way to make amount 0
for coin in coins:Iterate over each coin denomination
dp[w] += dp[w - coin]Add ways including current coin
public class Solution {
    public static int countWaysSpaceOpt(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int w = coin; w <= amount; w++) {
                dp[w] += dp[w - coin];
            }
        }
        return dp[amount];
    }
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        System.out.println(countWaysSpaceOpt(coins, amount));
    }
}
Line Notes
int[] dp = new int[amount + 1];Initialize 1D dp array
dp[0] = 1;Base case: one way to make amount 0
for (int coin : coins)Iterate over coins
dp[w] += dp[w - coin];Update ways including current coin
#include <iostream>
#include <vector>
using namespace std;

int countWaysSpaceOpt(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (int coin : coins) {
        for (int w = coin; w <= amount; w++) {
            dp[w] += dp[w - coin];
        }
    }
    return dp[amount];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amount = 5;
    cout << countWaysSpaceOpt(coins, amount) << endl;
    return 0;
}
Line Notes
vector<int> dp(amount + 1, 0);Initialize 1D dp vector
dp[0] = 1;Base case: one way to make amount 0
for (int coin : coins)Iterate over coins
dp[w] += dp[w - coin];Add ways including current coin
function countWaysSpaceOpt(coins, amount) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (const coin of coins) {
        for (let w = coin; w <= amount; w++) {
            dp[w] += dp[w - coin];
        }
    }
    return dp[amount];
}

const coins = [1, 2, 5];
const amount = 5;
console.log(countWaysSpaceOpt(coins, amount));
Line Notes
const dp = new Array(amount + 1).fill(0);Initialize 1D dp array
dp[0] = 1;Base case: one way to make amount 0
for (const coin of coins)Iterate over coins
dp[w] += dp[w - coin];Update ways including current coin
⏱
Complexity
TimeO(n * amount) iterating over coins and amounts
SpaceO(amount) reduced from 2D to 1D

Only one dp array is maintained, updated in place.

💡 For amount=1000, this uses 1000 integers instead of 100,000 in 2D.
Interview Verdict: Accepted

Space optimization is a common interview follow-up and shows deep understanding.

📊
All Approaches - One-Glance Tradeoffs
💡 In interviews, code the bottom-up tabulation or space-optimized approach for best balance of clarity and efficiency.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(2^n)O(n) recursion stackYes (deep recursion)YesMention only - never code
2. Top-Down MemoizationO(n * amount)O(n * amount)Possible but less likelyYesGood for explaining optimization
3. Bottom-Up TabulationO(n * amount)O(n * amount)NoYesPreferred approach to code
4. Space Optimized Bottom-UpO(n * amount)O(amount)NoNo (without extra tracking)Mention or code if asked for optimization
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and examples.Explain brute force recursion to show problem structure.Introduce memoization to optimize overlapping subproblems.Present bottom-up tabulation for iterative clarity.Discuss space optimization as an advanced technique.Write clean code and test edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Understanding of DP concepts, ability to optimize naive solutions, clarity in explanation, and coding accuracy.

Common Follow-ups

  • How to handle large amounts with modulo arithmetic → use modulo to avoid overflow.
  • Count permutations instead of combinations → change iteration order to count order-sensitive ways.
💡 These follow-ups test your flexibility with DP and understanding of problem variations.
🔍
Pattern Recognition

When to Use

1) Asked to count ways or number of combinations; 2) Unlimited use of items (coins); 3) Target sum or amount given; 4) Order of items does not matter.

Signature Phrases

number of ways to make changeunlimited supply of coinscount combinations

NOT This Pattern When

Problems asking for minimum coins or maximum value are optimization, not counting problems.

Similar Problems

Coin Change II - counts combinations similarlyCombination Sum IV - counts permutations (order matters)Partition Equal Subset Sum - subset sum feasibility

Practice

(1/5)
1. Consider the following code snippet implementing the optimal solution for the problem. Given the input strs = ["10", "0", "1"], m = 1, and n = 1, what is the final returned value?
easy
A. 2
B. 3
C. 1
D. 0

Solution

  1. Step 1: Trace dp updates for "10" (zeros=1, ones=1)

    dp[1][1] = max(dp[1][1], 1 + dp[0][0]) = 1
  2. Step 2: Trace dp updates for "0" (zeros=1, ones=0) and "1" (zeros=0, ones=1)

    After "0": dp[1][1] = max(1, 1 + dp[0][1]) = 1; After "1": dp[1][1] = max(1, 1 + dp[1][0]) = 1; Combining subsets "0" and "1" fits within limits, so dp[1][1] = 2
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Maximum subset size fitting m=1,n=1 is 2 [OK]
Hint: Trace dp from largest capacity down to zero [OK]
Common Mistakes:
  • Counting subsets incorrectly
  • Forgetting to iterate dp backwards
2. You are given a list of positive integers and a target sum. You need to determine if there exists a subset of these integers that sums exactly to the target. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. A greedy algorithm that picks the largest numbers first until the sum is reached or exceeded.
B. A dynamic programming approach that builds a boolean table tracking achievable sums up to the target.
C. A depth-first search that tries all subsets without memoization.
D. A sorting-based two-pointer technique to find pairs that sum to the target.

Solution

  1. Step 1: Understand problem constraints

    The problem requires checking if any subset sums exactly to a target, which is a classic subset sum problem.
  2. Step 2: Identify algorithm that guarantees correctness

    Greedy and two-pointer approaches fail because they do not consider all subsets. DFS without memoization is correct but inefficient. Dynamic programming builds a table of achievable sums, ensuring all subsets are considered efficiently.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DP tracks all sums up to target -> correct [OK]
Hint: Subset sum requires DP to track achievable sums [OK]
Common Mistakes:
  • Thinking greedy or sorting solves subset sum optimally
3. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the Equal Partition problem, where n is the number of elements and target is half the total sum?
medium
A. O(2^n) because the problem explores all subsets in worst case
B. O(n * n) because we iterate over all elements and all sums up to n
C. O(target^2) because the dp array size is target and we update it multiple times
D. O(n * target) because for each element we iterate over sums up to target

Solution

  1. Step 1: Identify loops in the code

    The outer loop runs n times (for each element), and the inner loop runs up to target times (half the total sum).
  2. Step 2: Calculate total time complexity

    Multiplying these gives O(n * target). The dp array updates are constant time per iteration.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Time depends on number of elements and target sum, not n squared or exponential [OK]
Hint: Time depends on n and target sum, not just n [OK]
Common Mistakes:
  • Confusing n with target or assuming quadratic in n
  • Forgetting target can be large
4. The following code attempts to solve the Partition to K Equal Sum Subsets problem using DP with bitmask tabulation. Identify the line containing the subtle bug that can cause incorrect results or infinite loops.
def canPartitionKSubsets(nums, k):
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    n = len(nums)
    nums.sort()
    if nums[-1] > target:
        return False

    dp = [-1] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == -1:
            continue
        for i in range(n):
            if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
                next_mask = mask | (1 << i)
                dp[next_mask] = (dp[mask] + nums[i]) % target

    return dp[(1 << n) - 1] == 0
medium
A. Line: dp = [-1] * (1 << n)
B. Line: if dp[next_mask] == -1: (missing in this code)
C. Line: nums.sort()
D. Line: dp[next_mask] = (dp[mask] + nums[i]) % target

Solution

  1. Step 1: Identify missing condition

    The code lacks a check if dp[next_mask] is already set, so it overwrites states, causing incorrect results.
  2. Step 2: Pinpoint the buggy line

    The line assigning dp[next_mask] unconditionally overwrites previous valid states, breaking memoization.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Adding "if dp[next_mask] == -1:" before assignment fixes bug [OK]
Hint: Always check if dp state is unset before assignment [OK]
Common Mistakes:
  • Overwriting dp states without checking leads to incorrect answers
  • Not pruning symmetric states increases runtime
5. Suppose the coin change problem is modified so that each coin can only be used at most once (0/1 knapsack variant). Which of the following changes to the bottom-up DP approach correctly solves this variant?
hard
A. Use a 2D dp array where dp[i][j] represents minimum coins to make amount j using first i coins, iterating coins outer and amounts inner
B. Sort coins and greedily pick largest coins without repetition until amount is reached
C. Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage)
D. Use the same 1D dp but iterate amounts outer and coins inner, updating dp[j] only if dp[j - coin] was from previous iteration

Solution

  1. Step 1: Understand the 0/1 usage constraint

    Each coin can be used once, so we must track usage per coin, requiring 2D dp.
  2. Step 2: Identify correct DP structure

    2D dp with dp[i][j] = min coins to make j using first i coins ensures no reuse; iterate coins outer, amounts inner.
  3. Step 3: Why other options fail

    Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage) allows unlimited reuse; B is greedy and incorrect; D misuses 1D dp which is for unbounded usage.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    0/1 knapsack requires 2D dp to track coin usage [OK]
Hint: 0/1 knapsack needs 2D dp to prevent reuse [OK]
Common Mistakes:
  • Using unbounded knapsack DP for 0/1 problem
  • Assuming greedy works for minimum coins
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard