Coin Change (Minimum Coins)

🎯

Coin Change (Minimum Coins)

mediumDPAmazonGoogleMicrosoft

Imagine you have an unlimited supply of coins of different denominations and you want to pay a certain amount using the fewest coins possible.

💡 This problem is a classic example of dynamic programming where beginners often struggle to see why greedy approaches fail and how to build solutions bottom-up or top-down with memoization.

📋

Problem Statement

Given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money, return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 2^31 - 10 ≤ amount ≤ 10^4

💡

Example

Input"coins = [1, 2, 5], amount = 11"

Output3

11 = 5 + 5 + 1, minimum coins needed is 3

Input"coins = [2], amount = 3"

Output-1

No combination of 2 can make 3

• amount = 0 → output 0 (no coins needed)
• coins = [1], amount = 0 → output 0 (zero amount)
• coins = [1], amount = 1 → output 1 (single coin equals amount)
• coins = [2, 5], amount = 3 → output -1 (impossible to form amount)

🔁

Why DP?

Why greedy fails:

Greedy fails because choosing the largest coin first does not always lead to the minimum number of coins. For example, amount=11 with coins=[1,5,7]: greedy picks 7 + 1 + 1 + 1 + 1 (5 coins), but optimal is 5 + 5 + 1 (3 coins).

DP state:

dp[i] represents the minimum number of coins needed to make amount i.

Recurrence:dp[i] = min(dp[i], 1 + dp[i - coin]) for each coin if i - coin >= 0

To find minimum coins for amount i, try each coin and add one coin to the minimum coins needed for amount i - coin, then take the minimum over all coins.

⚠️

Common Mistakes

Using greedy approach

Incorrect results for some inputs

✅ Use DP instead of greedy

Not handling amount=0 base case

Incorrect or infinite recursion

✅ Return 0 when amount is zero

Not checking for impossible amounts (returning infinity instead of -1)

Wrong output or runtime errors

✅ Return -1 if dp[amount] is infinity or max int

Using 2D DP unnecessarily

Wasted space and complexity

✅ Use 1D DP since only amount dimension matters

Not memoizing in top-down approach

TLE due to repeated calculations

✅ Add memo dictionary or map

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem's recursive structure and why naive solutions are inefficient due to repeated calculations.

Intuition

Try every coin for the current amount and recursively find the minimum coins needed for the remaining amount.

Algorithm

1. If amount is 0, return 0 because no coins are needed.
2. For each coin, recursively compute minimum coins needed for amount - coin.
3. Take the minimum among all recursive calls and add 1 for the current coin.
4. If no solution found, return -1.

💡 The recursion tree grows exponentially because it tries all coin combinations without caching results.

Recurrence:f(amount) = min(1 + f(amount - coin)) for all coins where amount - coin >= 0

</>

Code

def coinChange(coins, amount):
    def dfs(rem):
        if rem == 0:
            return 0
        if rem < 0:
            return float('inf')
        res = float('inf')
        for coin in coins:
            res = min(res, 1 + dfs(rem - coin))
        return res
    ans = dfs(amount)
    return ans if ans != float('inf') else -1

# Example usage
if __name__ == '__main__':
    print(coinChange([1,2,5], 11))  # Output: 3

Line Notes

def dfs(rem):Defines recursive helper to compute min coins for rem amount

if rem == 0:Base case: no coins needed for zero amount

if rem < 0:Invalid case: return infinity to exclude this path

for coin in coins:Try each coin to reduce the amount

res = min(res, 1 + dfs(rem - coin))Update minimum coins by choosing current coin plus recursive result

ans = dfs(amount)Start recursion from the target amount

return ans if ans != float('inf') else -1Return -1 if no solution found

import java.util.*;
public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        return dfs(coins, amount);
    }
    private static int dfs(int[] coins, int rem) {
        if (rem == 0) return 0;
        if (rem < 0) return Integer.MAX_VALUE;
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub = dfs(coins, rem - coin);
            if (sub != Integer.MAX_VALUE) {
                res = Math.min(res, 1 + sub);
            }
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1,2,5}, 11)); // 3
    }
}

Line Notes

public static int dfs(int[] coins, int rem)Recursive helper to find min coins for rem

if (rem == 0) return 0;Base case: zero coins needed for zero amount

if (rem < 0) return Integer.MAX_VALUE;Invalid path returns max value to exclude

for (int coin : coins)Try all coins to reduce amount

if (sub != Integer.MAX_VALUE)Check if recursive call returned valid result

res = Math.min(res, 1 + sub);Update minimum coins with current choice

return res;Return minimum coins found

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int dfs(const vector<int>& coins, int rem) {
    if (rem == 0) return 0;
    if (rem < 0) return INT_MAX;
    int res = INT_MAX;
    for (int coin : coins) {
        int sub = dfs(coins, rem - coin);
        if (sub != INT_MAX) {
            res = min(res, 1 + sub);
        }
    }
    return res;
}

int coinChange(vector<int>& coins, int amount) {
    int ans = dfs(coins, amount);
    return ans == INT_MAX ? -1 : ans;
}

int main() {
    vector<int> coins = {1,2,5};
    cout << coinChange(coins, 11) << endl; // 3
    return 0;
}

Line Notes

int dfs(const vector<int>& coins, int rem)Recursive function to compute min coins for rem

if (rem == 0) return 0;Base case: zero coins needed

if (rem < 0) return INT_MAX;Invalid path returns max int to exclude

for (int coin : coins)Try each coin to reduce amount

if (sub != INT_MAX)Check if recursive call is valid

res = min(res, 1 + sub);Update minimum coins with current choice

return ans == INT_MAX ? -1 : ans;Return -1 if no solution

function coinChange(coins, amount) {
    function dfs(rem) {
        if (rem === 0) return 0;
        if (rem < 0) return Infinity;
        let res = Infinity;
        for (let coin of coins) {
            res = Math.min(res, 1 + dfs(rem - coin));
        }
        return res;
    }
    const ans = dfs(amount);
    return ans === Infinity ? -1 : ans;
}

// Example usage
console.log(coinChange([1,2,5], 11)); // 3

Line Notes

function dfs(rem)Recursive helper to find min coins for rem

if (rem === 0) return 0;Base case: zero coins needed

if (rem < 0) return Infinity;Invalid path returns Infinity to exclude

for (let coin of coins)Try all coins to reduce amount

res = Math.min(res, 1 + dfs(rem - coin));Update minimum coins with current choice

const ans = dfs(amount);Start recursion from amount

return ans === Infinity ? -1 : ans;Return -1 if no solution

⏱

Complexity

TimeO(S^n) where S is amount and n is number of coins due to exponential recursion

SpaceO(S) recursion stack depth

Each amount calls all coins recursively leading to exponential calls

💡 For amount=20 and 3 coins, this can lead to millions of calls, making it impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's recursive nature.

🧠

Top-Down Memoization

💡 Memoization caches results of subproblems to avoid repeated work, drastically improving efficiency over brute force.

Intuition

Use recursion but store results for each amount so that repeated calls return cached answers instantly.

Algorithm

1. Initialize a memo dictionary to store minimum coins for each amount.
2. If amount is 0, return 0.
3. If amount is negative, return infinity.
4. If amount is in memo, return stored result.
5. For each coin, recursively compute minimum coins for amount - coin and update minimum.
6. Store and return the minimum coins for current amount.

💡 Memoization reduces exponential calls to polynomial by caching results.

Recurrence:f(amount) = min(1 + f(amount - coin)) for all coins, with memoization

</>

Code

def coinChange(coins, amount):
    memo = {}
    def dfs(rem):
        if rem == 0:
            return 0
        if rem < 0:
            return float('inf')
        if rem in memo:
            return memo[rem]
        res = float('inf')
        for coin in coins:
            res = min(res, 1 + dfs(rem - coin))
        memo[rem] = res
        return res
    ans = dfs(amount)
    return ans if ans != float('inf') else -1

if __name__ == '__main__':
    print(coinChange([1,2,5], 11))  # 3

Line Notes

memo = {}Initialize cache to store results for amounts

if rem in memo:Return cached result if available

memo[rem] = resStore computed result to avoid recomputation

res = min(res, 1 + dfs(rem - coin))Try all coins and pick minimum

ans = dfs(amount)Start recursion from target amount

return ans if ans != float('inf') else -1Return -1 if no solution

import java.util.*;
public class CoinChange {
    private static Map<Integer, Integer> memo = new HashMap<>();
    public static int coinChange(int[] coins, int amount) {
        int res = dfs(coins, amount);
        return res == Integer.MAX_VALUE ? -1 : res;
    }
    private static int dfs(int[] coins, int rem) {
        if (rem == 0) return 0;
        if (rem < 0) return Integer.MAX_VALUE;
        if (memo.containsKey(rem)) return memo.get(rem);
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub = dfs(coins, rem - coin);
            if (sub != Integer.MAX_VALUE) {
                res = Math.min(res, 1 + sub);
            }
        }
        memo.put(rem, res);
        return res;
    }
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1,2,5}, 11)); // 3
    }
}

Line Notes

private static Map<Integer, Integer> memo = new HashMap<>();Cache results for amounts

if (memo.containsKey(rem)) return memo.get(rem);Return cached result if present

memo.put(rem, res);Store computed result

res = Math.min(res, 1 + sub);Try all coins and update minimum

return res;Return minimum coins for rem

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

unordered_map<int,int> memo;

int dfs(const vector<int>& coins, int rem) {
    if (rem == 0) return 0;
    if (rem < 0) return INT_MAX;
    if (memo.count(rem)) return memo[rem];
    int res = INT_MAX;
    for (int coin : coins) {
        int sub = dfs(coins, rem - coin);
        if (sub != INT_MAX) {
            res = min(res, 1 + sub);
        }
    }
    memo[rem] = res;
    return res;
}

int coinChange(vector<int>& coins, int amount) {
    int ans = dfs(coins, amount);
    return ans == INT_MAX ? -1 : ans;
}

int main() {
    vector<int> coins = {1,2,5};
    cout << coinChange(coins, 11) << endl; // 3
    return 0;
}

Line Notes

unordered_map<int,int> memo;Cache for storing results

if (memo.count(rem)) return memo[rem];Return cached result if exists

memo[rem] = res;Store computed minimum coins

res = min(res, 1 + sub);Try all coins and update minimum

return ans == INT_MAX ? -1 : ans;Return -1 if no solution

function coinChange(coins, amount) {
    const memo = new Map();
    function dfs(rem) {
        if (rem === 0) return 0;
        if (rem < 0) return Infinity;
        if (memo.has(rem)) return memo.get(rem);
        let res = Infinity;
        for (let coin of coins) {
            res = Math.min(res, 1 + dfs(rem - coin));
        }
        memo.set(rem, res);
        return res;
    }
    const ans = dfs(amount);
    return ans === Infinity ? -1 : ans;
}

console.log(coinChange([1,2,5], 11)); // 3

Line Notes

const memo = new Map();Cache results for amounts

if (memo.has(rem)) return memo.get(rem);Return cached result if available

memo.set(rem, res);Store computed result

res = Math.min(res, 1 + dfs(rem - coin));Try all coins and update minimum

return ans === Infinity ? -1 : ans;Return -1 if no solution

⏱

Complexity

TimeO(amount * n) where n is number of coins due to memoization

SpaceO(amount) for memo and recursion stack

Each amount is computed once and stored, reducing exponential calls to linear in amount

💡 For amount=20 and 3 coins, this reduces calls from millions to about 60.

Interview Verdict: Accepted

This approach is efficient enough for typical interview constraints and demonstrates DP memoization well.

🧠

Bottom-Up Tabulation (Iterative DP)

💡 This approach builds the solution from the smallest subproblems up to the target amount, avoiding recursion and making the process clearer and often faster.

Intuition

Create a dp array where dp[i] stores minimum coins needed for amount i, and fill it iteratively from 0 to amount.

Algorithm

1. Initialize dp array of size amount+1 with infinity, except dp[0] = 0.
2. For each amount i from 1 to amount, try each coin.
3. If coin <= i, update dp[i] = min(dp[i], 1 + dp[i - coin]).
4. After filling dp, if dp[amount] is infinity, return -1; else return dp[amount].

💡 This approach ensures all subproblems are solved once in a systematic order.

Recurrence:dp[i] = min(dp[i], 1 + dp[i - coin]) for all coins where i - coin >= 0

</>

Code

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount] if dp[amount] != float('inf') else -1

if __name__ == '__main__':
    print(coinChange([1,2,5], 11))  # 3

Line Notes

dp = [float('inf')] * (amount + 1)Initialize dp array with infinity to represent unreachable amounts

dp[0] = 0Zero coins needed to make amount zero

for i in range(1, amount + 1)Iterate over all amounts from 1 to target

if coin <= iOnly consider coins that can fit into current amount

dp[i] = min(dp[i], 1 + dp[i - coin])Update dp[i] with minimum coins using current coin

return dp[amount] if dp[amount] != float('inf') else -1Return result or -1 if no solution

import java.util.*;
public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1,2,5}, 11)); // 3
    }
}

Line Notes

int[] dp = new int[amount + 1];Create dp array for amounts

Arrays.fill(dp, Integer.MAX_VALUE);Initialize dp with max value to represent unreachable

dp[0] = 0;Zero coins needed for amount zero

if (coin <= i && dp[i - coin] != Integer.MAX_VALUE)Check coin fits and subproblem is solvable

dp[i] = Math.min(dp[i], 1 + dp[i - coin]);Update dp[i] with minimum coins

return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];Return result or -1

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], 1 + dp[i - coin]);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1,2,5};
    cout << coinChange(coins, 11) << endl; // 3
    return 0;
}

Line Notes

vector<int> dp(amount + 1, INT_MAX);Initialize dp array with max int

dp[0] = 0;Zero coins needed for zero amount

if (coin <= i && dp[i - coin] != INT_MAX)Check coin fits and subproblem solvable

dp[i] = min(dp[i], 1 + dp[i - coin]);Update dp[i] with minimum coins

return dp[amount] == INT_MAX ? -1 : dp[amount];Return result or -1

function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1,2,5], 11)); // 3

Line Notes

const dp = new Array(amount + 1).fill(Infinity);Initialize dp array with Infinity

dp[0] = 0;Zero coins needed for zero amount

if (coin <= i)Check coin fits into current amount

dp[i] = Math.min(dp[i], 1 + dp[i - coin]);Update dp[i] with minimum coins

return dp[amount] === Infinity ? -1 : dp[amount];Return result or -1

⏱

Complexity

TimeO(amount * n) where n is number of coins

SpaceO(amount) for dp array

Each amount is computed once by checking all coins

💡 For amount=20 and 3 coins, about 60 operations, very efficient.

Interview Verdict: Accepted

This is the standard optimal DP solution for this problem in interviews.

🧠

Space Optimized Bottom-Up (1D DP)

💡 Since the problem only depends on previous states in a 1D array, we can optimize space by using a single dp array without extra dimensions.

Intuition

Use a single dp array to store minimum coins for each amount and update it iteratively.

Algorithm

1. Initialize dp array of size amount+1 with infinity, except dp[0] = 0.
2. Iterate amounts from 1 to amount.
3. For each coin, if coin <= current amount, update dp[current amount] with min of current and 1 + dp[current amount - coin].
4. Return dp[amount] if reachable, else -1.

💡 This approach uses minimal memory while maintaining the same logic as tabulation.

Recurrence:dp[i] = min(dp[i], 1 + dp[i - coin]) for all coins where i - coin >= 0

</>

Code

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount] if dp[amount] != float('inf') else -1

if __name__ == '__main__':
    print(coinChange([1,2,5], 11))  # 3

Line Notes

dp = [float('inf')] * (amount + 1)Initialize dp with infinity to represent unreachable amounts

dp[0] = 0Zero coins needed for zero amount

for i in range(1, amount + 1)Iterate over all amounts

if coin <= iCheck if coin can be used for current amount

dp[i] = min(dp[i], 1 + dp[i - coin])Update dp[i] with minimum coins

return dp[amount] if dp[amount] != float('inf') else -1Return result or -1

import java.util.*;
public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1,2,5}, 11)); // 3
    }
}

Line Notes

int[] dp = new int[amount + 1];Create dp array for amounts

Arrays.fill(dp, Integer.MAX_VALUE);Initialize dp with max value

dp[0] = 0;Zero coins needed for zero amount

if (coin <= i && dp[i - coin] != Integer.MAX_VALUE)Check coin fits and subproblem solvable

dp[i] = Math.min(dp[i], 1 + dp[i - coin]);Update dp[i] with minimum coins

return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];Return result or -1

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], 1 + dp[i - coin]);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1,2,5};
    cout << coinChange(coins, 11) << endl; // 3
    return 0;
}

Line Notes

vector<int> dp(amount + 1, INT_MAX);Initialize dp array with max int

dp[0] = 0;Zero coins needed for zero amount

if (coin <= i && dp[i - coin] != INT_MAX)Check coin fits and subproblem solvable

dp[i] = min(dp[i], 1 + dp[i - coin]);Update dp[i] with minimum coins

return dp[amount] == INT_MAX ? -1 : dp[amount];Return result or -1

function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1,2,5], 11)); // 3

Line Notes

const dp = new Array(amount + 1).fill(Infinity);Initialize dp with Infinity

dp[0] = 0;Zero coins needed for zero amount

if (coin <= i)Check coin fits into current amount

dp[i] = Math.min(dp[i], 1 + dp[i - coin]);Update dp[i] with minimum coins

return dp[amount] === Infinity ? -1 : dp[amount];Return result or -1

⏱

Complexity

TimeO(amount * n) where n is number of coins

SpaceO(amount) for dp array

Same as tabulation but uses minimal memory

💡 This is the most memory-efficient standard DP solution.

Interview Verdict: Accepted

This is the preferred approach in interviews for its clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding bottom-up tabulation or memoization is best; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	Exponential	O(amount) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Top-Down Memoization	O(amount * n)	O(amount) memo + recursion stack	Possible for large amount	Yes with extra tracking	Good for explaining optimization
3. Bottom-Up Tabulation	O(amount * n)	O(amount)	No	Yes with extra tracking	Preferred approach to code
4. Space Optimized Bottom-Up	O(amount * n)	O(amount)	No	Yes with extra tracking	Mention as 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

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force recursive approach to show understanding.Step 3: Introduce memoization to optimize recursion.Step 4: Present bottom-up tabulation as the optimal iterative solution.Step 5: Optionally mention space optimization for memory efficiency.Step 6: Code the chosen approach carefully and test with examples.

Time Allocation

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

What the Interviewer Tests

Understanding of recursion and DP, ability to optimize naive solutions, clarity in explaining tradeoffs, and clean coding skills.

Common Follow-ups

• What if you want to count the number of ways to make the amount? → Use a different DP formulation.
• How to reconstruct the coins used? → Store choices during DP and backtrack.

💡 These follow-ups test deeper understanding of DP variations and solution reconstruction.

🔍

Pattern Recognition

When to Use

1) Problem asks for minimum or maximum using unlimited items, 2) Choices can be repeated, 3) Problem can be broken into smaller subproblems by reducing amount, 4) Overlapping subproblems exist.

Signature Phrases

'fewest number of coins''unlimited supply of coins''make up that amount'

NOT This Pattern When

Problems with limited items or no repetition are 0/1 knapsack, not unbounded.

Similar Problems

Coin Change 2 - counts number of ways instead of minimum coinsRod Cutting - similar unbounded knapsack with lengthsMinimum Number of Squares - similar DP minimization problem

Practice

1. Given the following code for lastStoneWeightII, what is the returned value when stones = [1, 2, 3]?

easy

A. 1

B. 0

C. 2

D. 3

Solution

1. Step 1: Calculate total and half

   Total = 6, half = 3. dp array size = 4, dp[0] = true initially.

2. Step 2: Update dp for each stone

   For weight=1: dp[1]=true; for weight=2: dp[3]=true (since dp[1] was true), dp[2]=true; for weight=3: dp[3]=true remains.

3. Step 3: Find largest w ≤ half with dp[w] = true

   dp[3] is true, so minimal difference = total - 2*3 = 6 - 6 = 0.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Subset {1,2,3} sums to 6; partition into {3} and {1,2} sums 3 and 3 -> difference 0 [OK]

Hint: Check dp array for sums up to half total [OK]

Common Mistakes:

• Returning total instead of minimal difference
• Off-by-one error in dp indexing
• Not iterating backwards in dp update

2. What is the time complexity of the space-optimized bottom-up subset sum algorithm given an input list of size n and target sum S?

medium

A. O(2^n)

B. O(n + S)

C. O(n * S)

D. O(n * log S)

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm has an outer loop over n elements and an inner loop over sums from S down to each num.

2. Step 2: Calculate total operations

   Each element causes up to S iterations, so total time is O(n * S). Recursive brute force is exponential, and linear or log factors are incorrect.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops over n and S -> O(n * S) [OK]

Hint: Nested loops over n and S -> multiply complexities [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming linear or exponential time incorrectly

3. The following code attempts to solve the Target Sum problem using bottom-up DP with offset indexing. Which line contains a subtle bug that causes incorrect results on inputs containing zero?

medium

A. Line 12-15: Updating dp array in-place instead of using a separate next_dp

B. Line 6: dp[offset] = 1

C. Line 10: if dp[s] != 0:

D. Line 8: for num in nums:

Solution

1. Step 1: Identify DP update method

   The code updates dp in-place during iteration over sums, causing double counting when num=0 or overlapping states.

2. Step 2: Understand impact on zero values

   Zero does not change sum, so updating dp in-place doubles counts incorrectly. Using a separate next_dp array avoids this.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   In-place updates cause state reuse within iteration, breaking correctness [OK]

Hint: In-place dp updates cause double counting with zero values [OK]

Common Mistakes:

• Not using a separate dp array for next iteration

4. Suppose now you want to count the number of ways to make change but coins can be used at most once each (no reuse). Which modification to the DP approach correctly solves this variant?

hard

A. Use 1D DP iterating amounts forwards but reset dp array after each coin

B. Use 2D DP with dp[i][w] representing ways using first i coins for amount w, iterating amounts forwards

C. Use the same 1D DP but iterate amounts backwards from amount down to coin value

D. Use greedy approach picking largest coins first until amount is reached

Solution

1. Step 1: Understand no reuse constraint

   Each coin can be used once, so combinations must not count repeated usage of the same coin.

2. Step 2: Modify DP iteration order

   Iterating amounts backwards in 1D DP ensures each coin contributes only once per amount, preventing reuse.

3. Step 3: Confirm correctness

   This approach correctly counts combinations without reuse, unlike forward iteration which allows multiple usage.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Backward iteration in 1D DP enforces single usage per coin [OK]

Hint: Backward iteration prevents coin reuse in 1D DP [OK]

Common Mistakes:

• Using forward iteration allows unlimited reuse
• Resetting dp array loses accumulated counts
• Greedy approach misses many combinations

5. Suppose the Target Sum problem is modified so that each number in the array can be used multiple times (unlimited reuse). Which of the following changes correctly adapts the DP solution to this variant?

hard

A. Use a 1D dp array and update dp in forward order for each num to allow reuse

B. Keep the same DP with offset and update dp in reverse order to avoid double counting

C. Use a 2D dp array with dimensions n and sum, but only update dp[i][s] from dp[i-1][s-num]

D. Switch to a brute force recursion since DP cannot handle reuse

Solution

1. Step 1: Understand reuse impact on DP iteration

   Allowing unlimited reuse means for each num, dp must be updated in forward order so that dp[s-num] includes ways using current num multiple times.

2. Step 2: Identify correct DP update order

   Backward iteration prevents reuse by only using previous states. Forward iteration accumulates counts correctly for unlimited usage.

3. Step 3: Evaluate options

   Use a 1D dp array and update dp in forward order for each num to allow reuse correctly updates dp forward. Keep the same DP with offset and update dp in reverse order to avoid double counting backward iteration is for no reuse. Use a 2D dp array with dimensions n and sum, but only update dp[i][s] from dp[i-1][s-num] restricts to previous items only. Switch to a brute force recursion since DP cannot handle reuse is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Forward dp update enables multiple usage of same number [OK]

Hint: Forward dp iteration enables unlimited reuse [OK]

Common Mistakes:

• Using backward iteration which forbids reuse