0/1 Knapsack Problem

🎯

0/1 Knapsack Problem

mediumDPAmazonGoogleMicrosoft

Imagine you are a thief with a knapsack that can carry a limited weight. You want to maximize the total value of items you steal without exceeding the weight limit.

💡 This problem is a classic example of combinatorial optimization where you must decide whether to include or exclude each item. Beginners often struggle because the naive approach tries all subsets, which is exponential, and understanding how to optimize with dynamic programming requires grasping overlapping subproblems and optimal substructure.

📋

Problem Statement

Given n items, each with a weight and a value, determine the maximum total value of items you can include in a knapsack of capacity W. You can either include or exclude each item (no partial items allowed). Input: integer n, integer W, arrays weights and values of length n. Output: maximum value achievable without exceeding weight W.

1 ≤ n ≤ 10001 ≤ W ≤ 10^51 ≤ weights[i], values[i] ≤ 10^5

💡

Example

Input"n = 3, W = 50, weights = [10, 20, 30], values = [60, 100, 120]"

Output220

Choose items with weights 20 and 30 for total value 100 + 120 = 220 without exceeding capacity 50.

• n = 1, W = weight of the single item → output is value if fits, else 0
• All items heavier than W → output 0
• All items fit into W → output sum of all values
• W = 0 → output 0

🔁

Why DP?

Why greedy fails:

A greedy approach that picks items with the highest value or value-to-weight ratio first can fail. For example, items with high value but heavy weight might block better combinations of lighter items with better total value.

DP state:

dp[i][w] represents the maximum value achievable using the first i items with a knapsack capacity of w.

Recurrence:dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]) if weights[i-1] ≤ w else dp[i-1][w]

For each item, either skip it (dp[i-1][w]) or include it if it fits (dp[i-1][w - weight] + value), and take the better option.

⚠️

Common Mistakes

Not handling base cases correctly

Incorrect results or runtime errors

✅ Explicitly check for zero items or zero capacity

Iterating forwards in space optimized approach

Overcounting items, wrong answers

✅ Iterate backwards over capacities when updating dp array

Using 1-based indexing inconsistently

Index errors or off-by-one bugs

✅ Be consistent with indexing items and dp arrays

Not memoizing all parameters in recursion

Memoization ineffective, TLE

✅ Use both item index and capacity as memo keys

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's combinatorial nature and why naive solutions are inefficient, setting the stage for dynamic programming.

Intuition

Try every combination of including or excluding each item recursively and pick the best total value that fits in the knapsack.

Algorithm

1. Start from the first item and current capacity.
2. Recursively explore two choices: include the item if it fits, or exclude it.
3. Return the maximum value from these two choices.
4. Base case: no items left or capacity zero.

💡 The recursion tree grows exponentially because each item doubles the number of subproblems.

Recurrence:f(i, w) = max(f(i-1, w), f(i-1, w - weights[i-1]) + values[i-1]) if weights[i-1] ≤ w else f(i-1, w)

</>

Code

def knapsack_recursive(i, w, weights, values):
    if i == 0 or w == 0:
        return 0
    if weights[i-1] > w:
        return knapsack_recursive(i-1, w, weights, values)
    else:
        return max(knapsack_recursive(i-1, w, weights, values),
                   knapsack_recursive(i-1, w - weights[i-1], weights, values) + values[i-1])

# Driver code
if __name__ == '__main__':
    weights = [10, 20, 30]
    values = [60, 100, 120]
    W = 50
    n = len(weights)
    print(knapsack_recursive(n, W, weights, values))

Line Notes

if i == 0 or w == 0:Base case: no items or no capacity means zero value

if weights[i-1] > w:If current item doesn't fit, skip it

return max(knapsack_recursive(i-1, w, weights, values),Option 1: exclude current item

knapsack_recursive(i-1, w - weights[i-1], weights, values) + values[i-1])Option 2: include current item and add its value

public class Knapsack {
    public static int knapsackRecursive(int i, int w, int[] weights, int[] values) {
        if (i == 0 || w == 0) return 0;
        if (weights[i - 1] > w) {
            return knapsackRecursive(i - 1, w, weights, values);
        } else {
            return Math.max(knapsackRecursive(i - 1, w, weights, values),
                            knapsackRecursive(i - 1, w - weights[i - 1], weights, values) + values[i - 1]);
        }
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int W = 50;
        int n = weights.length;
        System.out.println(knapsackRecursive(n, W, weights, values));
    }
}

Line Notes

if (i == 0 || w == 0) return 0;Base case: no items or capacity means zero value

if (weights[i - 1] > w)Skip item if it doesn't fit

Math.max(knapsackRecursive(i - 1, w, weights, values),Exclude current item option

knapsackRecursive(i - 1, w - weights[i - 1], weights, values) + values[i - 1]Include current item option

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

int knapsackRecursive(int i, int w, const vector<int>& weights, const vector<int>& values) {
    if (i == 0 || w == 0) return 0;
    if (weights[i - 1] > w) {
        return knapsackRecursive(i - 1, w, weights, values);
    } else {
        return max(knapsackRecursive(i - 1, w, weights, values),
                   knapsackRecursive(i - 1, w - weights[i - 1], weights, values) + values[i - 1]);
    }
}

int main() {
    vector<int> weights = {10, 20, 30};
    vector<int> values = {60, 100, 120};
    int W = 50;
    int n = weights.size();
    cout << knapsackRecursive(n, W, weights, values) << endl;
    return 0;
}

Line Notes

if (i == 0 || w == 0) return 0;Base case: no items or capacity means zero value

if (weights[i - 1] > w)Skip item if it doesn't fit

max(knapsackRecursive(i - 1, w, weights, values),Exclude current item option

knapsackRecursive(i - 1, w - weights[i - 1], weights, values) + values[i - 1]Include current item option

function knapsackRecursive(i, w, weights, values) {
    if (i === 0 || w === 0) return 0;
    if (weights[i - 1] > w) {
        return knapsackRecursive(i - 1, w, weights, values);
    } else {
        return Math.max(knapsackRecursive(i - 1, w, weights, values),
                        knapsackRecursive(i - 1, w - weights[i - 1], weights, values) + values[i - 1]);
    }
}

// Driver code
const weights = [10, 20, 30];
const values = [60, 100, 120];
const W = 50;
const n = weights.length;
console.log(knapsackRecursive(n, W, weights, values));

Line Notes

if (i === 0 || w === 0) return 0;Base case: no items or capacity means zero value

if (weights[i - 1] > w)Skip item if it doesn't fit

Math.max(knapsackRecursive(i - 1, w, weights, values),Exclude current item option

knapsackRecursive(i - 1, w - weights[i - 1], weights, values) + values[i - 1]Include current item option

⏱

Complexity

TimeO(2^n)

SpaceO(n) due to recursion stack

Each item has two choices, leading to 2^n combinations. The recursion stack depth is n.

💡 For n=20, this means over a million calls, which is too slow for interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand before optimizing.

🧠

Top-Down Memoization

💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving efficiency while keeping the recursive structure.

Intuition

Use recursion but store results for each (i, w) state to avoid repeated work.

Algorithm

1. Initialize a 2D cache for states (i, w).
2. Recursively compute max value for each state, returning cached results if available.
3. For each item, decide to include or exclude it if it fits.
4. Return the cached maximum value for the full problem.

💡 Memoization prunes the recursion tree by remembering answers to subproblems.

Recurrence:Same as brute force: f(i, w) = max(f(i-1, w), f(i-1, w - weights[i-1]) + values[i-1]) if weights[i-1] ≤ w else f(i-1, w)

</>

Code

def knapsack_memo(i, w, weights, values, memo):
    if i == 0 or w == 0:
        return 0
    if (i, w) in memo:
        return memo[(i, w)]
    if weights[i-1] > w:
        memo[(i, w)] = knapsack_memo(i-1, w, weights, values, memo)
    else:
        memo[(i, w)] = max(knapsack_memo(i-1, w, weights, values, memo),
                           knapsack_memo(i-1, w - weights[i-1], weights, values, memo) + values[i-1])
    return memo[(i, w)]

# Driver code
if __name__ == '__main__':
    weights = [10, 20, 30]
    values = [60, 100, 120]
    W = 50
    n = len(weights)
    memo = {}
    print(knapsack_memo(n, W, weights, values, memo))

Line Notes

if (i, w) in memo:Check if result already computed to avoid recomputation

memo[(i, w)] = knapsack_memo(i-1, w, weights, values, memo)Store result when skipping item

memo[(i, w)] = max(...)Store result when choosing best of include/exclude

return memo[(i, w)]Return cached or newly computed result

import java.util.HashMap;
import java.util.Map;

public class Knapsack {
    static Map<String, Integer> memo = new HashMap<>();

    public static int knapsackMemo(int i, int w, int[] weights, int[] values) {
        if (i == 0 || w == 0) return 0;
        String key = i + "," + w;
        if (memo.containsKey(key)) return memo.get(key);
        int result;
        if (weights[i - 1] > w) {
            result = knapsackMemo(i - 1, w, weights, values);
        } else {
            result = Math.max(knapsackMemo(i - 1, w, weights, values),
                              knapsackMemo(i - 1, w - weights[i - 1], weights, values) + values[i - 1]);
        }
        memo.put(key, result);
        return result;
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int W = 50;
        int n = weights.length;
        System.out.println(knapsackMemo(n, W, weights, values));
    }
}

Line Notes

if (memo.containsKey(key)) return memo.get(key);Return cached result if available

memo.put(key, result);Cache computed result for current state

if (weights[i - 1] > w)Skip item if it doesn't fit

Math.max(knapsackMemo(i - 1, w, weights, values),Choose max of exclude/include

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

unordered_map<string, int> memo;

int knapsackMemo(int i, int w, const vector<int>& weights, const vector<int>& values) {
    if (i == 0 || w == 0) return 0;
    string key = to_string(i) + "," + to_string(w);
    if (memo.find(key) != memo.end()) return memo[key];
    if (weights[i - 1] > w) {
        memo[key] = knapsackMemo(i - 1, w, weights, values);
    } else {
        memo[key] = max(knapsackMemo(i - 1, w, weights, values),
                        knapsackMemo(i - 1, w - weights[i - 1], weights, values) + values[i - 1]);
    }
    return memo[key];
}

int main() {
    vector<int> weights = {10, 20, 30};
    vector<int> values = {60, 100, 120};
    int W = 50;
    int n = weights.size();
    cout << knapsackMemo(n, W, weights, values) << endl;
    return 0;
}

Line Notes

if (memo.find(key) != memo.end()) return memo[key];Return cached result if available

memo[key] = knapsackMemo(i - 1, w, weights, values);Cache result when skipping item

memo[key] = max(...)Cache result when choosing best option

return memo[key];Return cached or computed result

const memo = new Map();

function knapsackMemo(i, w, weights, values) {
    if (i === 0 || w === 0) return 0;
    const key = i + ',' + w;
    if (memo.has(key)) return memo.get(key);
    let result;
    if (weights[i - 1] > w) {
        result = knapsackMemo(i - 1, w, weights, values);
    } else {
        result = Math.max(knapsackMemo(i - 1, w, weights, values),
                          knapsackMemo(i - 1, w - weights[i - 1], weights, values) + values[i - 1]);
    }
    memo.set(key, result);
    return result;
}

// Driver code
const weights = [10, 20, 30];
const values = [60, 100, 120];
const W = 50;
const n = weights.length;
console.log(knapsackMemo(n, W, weights, values));

Line Notes

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

memo.set(key, result);Cache computed result for reuse

if (weights[i - 1] > w)Skip item if it doesn't fit

Math.max(knapsackMemo(i - 1, w, weights, values),Choose max of exclude/include

⏱

Complexity

TimeO(n * W)

SpaceO(n * W) due to memoization cache and recursion stack

Each state (i, w) is computed once and stored, reducing exponential calls to polynomial.

💡 For n=1000 and W=1000, this means about 1 million states, which is feasible.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for typical constraints.

🧠

Bottom-Up Tabulation

💡 Tabulation builds the solution iteratively from smaller subproblems, which is often easier to understand and avoids recursion overhead.

Intuition

Create a 2D dp table where each cell dp[i][w] stores the max value using first i items and capacity w, filling it row by row.

Algorithm

1. Initialize a 2D dp array of size (n+1) x (W+1) with zeros.
2. Iterate over items from 1 to n.
3. For each capacity from 0 to W, decide to include or exclude the current item.
4. Fill dp[i][w] with the maximum value achievable.
5. Return dp[n][W] as the final answer.

💡 This approach systematically solves all subproblems in increasing order of items and capacities.

Recurrence:dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]) if weights[i-1] ≤ w else dp[i-1][w]

</>

Code

def knapsack_tabulation(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][W]

# Driver code
if __name__ == '__main__':
    weights = [10, 20, 30]
    values = [60, 100, 120]
    W = 50
    print(knapsack_tabulation(weights, values, W))

Line Notes

dp = [[0] * (W + 1) for _ in range(n + 1)]Initialize dp table with zeros for base cases

for i in range(1, n + 1):Iterate over items starting from 1

if weights[i - 1] <= w:Check if current item fits in capacity w

dp[i][w] = max(...)Choose max of excluding or including current item

public class Knapsack {
    public static int knapsackTabulation(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[][] dp = new int[n + 1][W + 1];
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int W = 50;
        System.out.println(knapsackTabulation(weights, values, W));
    }
}

Line Notes

int[][] dp = new int[n + 1][W + 1];Create dp table with base cases initialized to zero

for (int i = 1; i <= n; i++) {Iterate over items

if (weights[i - 1] <= w) {Check if item fits in current capacity

dp[i][w] = Math.max(...)Choose max of excluding or including item

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

int knapsackTabulation(const vector<int>& weights, const vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

int main() {
    vector<int> weights = {10, 20, 30};
    vector<int> values = {60, 100, 120};
    int W = 50;
    cout << knapsackTabulation(weights, values, W) << endl;
    return 0;
}

Line Notes

vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));Initialize dp table with zeros

for (int i = 1; i <= n; i++) {Iterate over items

if (weights[i - 1] <= w) {Check if item fits

dp[i][w] = max(...)Choose max of excluding or including item

function knapsackTabulation(weights, values, W) {
    const n = weights.length;
    const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        for (let w = 0; w <= W; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

// Driver code
const weights = [10, 20, 30];
const values = [60, 100, 120];
const W = 50;
console.log(knapsackTabulation(weights, values, W));

Line Notes

const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));Initialize 2D dp array with zeros

for (let i = 1; i <= n; i++) {Iterate over items

if (weights[i - 1] <= w) {Check if item fits in capacity

dp[i][w] = Math.max(...)Choose max of excluding or including item

⏱

Complexity

TimeO(n * W)

SpaceO(n * W)

We fill a table of size n by W once, each cell computed in O(1).

💡 For n=1000 and W=1000, this means about 1 million operations, which is efficient.

Interview Verdict: Accepted

This is the standard efficient solution for the 0/1 knapsack problem.

🧠

Space Optimized Bottom-Up

💡 Since dp[i][w] depends only on dp[i-1][...], we can reduce space from O(n*W) to O(W) by iterating backwards over capacities.

Intuition

Use a 1D dp array where dp[w] stores max value for capacity w, updating it in reverse order for each item.

Algorithm

1. Initialize a 1D dp array of size W+1 with zeros.
2. For each item, iterate capacities from W down to the item's weight.
3. Update dp[w] as max of current dp[w] and dp[w - weight] + value.
4. Return dp[W] as the maximum value.

💡 Backward iteration ensures we use results from the previous item iteration, preventing reuse of updated states.

Recurrence:dp[w] = max(dp[w], dp[w - weights[i-1]] + values[i-1]) for w ≥ weights[i-1]

</>

Code

def knapsack_space_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# Driver code
if __name__ == '__main__':
    weights = [10, 20, 30]
    values = [60, 100, 120]
    W = 50
    print(knapsack_space_optimized(weights, values, W))

Line Notes

dp = [0] * (W + 1)Initialize 1D dp array for capacities

for i in range(n):Iterate over each item

for w in range(W, weights[i] - 1, -1):Iterate backwards over capacities to avoid reuse

dp[w] = max(dp[w], dp[w - weights[i]] + values[i])Update dp[w] with max value including current item

public class Knapsack {
    public static int knapsackSpaceOptimized(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[] dp = new int[W + 1];
        for (int i = 0; i < n; i++) {
            for (int w = W; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        return dp[W];
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int W = 50;
        System.out.println(knapsackSpaceOptimized(weights, values, W));
    }
}

Line Notes

int[] dp = new int[W + 1];Initialize 1D dp array for capacities

for (int i = 0; i < n; i++) {Iterate over items

for (int w = W; w >= weights[i]; w--) {Iterate backwards over capacities

dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);Update dp[w] with max value including current item

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

int knapsackSpaceOptimized(const vector<int>& weights, const vector<int>& values, int W) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

int main() {
    vector<int> weights = {10, 20, 30};
    vector<int> values = {60, 100, 120};
    int W = 50;
    cout << knapsackSpaceOptimized(weights, values, W) << endl;
    return 0;
}

Line Notes

vector<int> dp(W + 1, 0);Initialize 1D dp array with zeros

for (int i = 0; i < n; i++) {Iterate over items

for (int w = W; w >= weights[i]; w--) {Iterate backwards over capacities

dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);Update dp[w] with max value including current item

function knapsackSpaceOptimized(weights, values, W) {
    const n = weights.length;
    const dp = new Array(W + 1).fill(0);
    for (let i = 0; i < n; i++) {
        for (let w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

// Driver code
const weights = [10, 20, 30];
const values = [60, 100, 120];
const W = 50;
console.log(knapsackSpaceOptimized(weights, values, W));

Line Notes

const dp = new Array(W + 1).fill(0);Initialize 1D dp array for capacities

for (let i = 0; i < n; i++) {Iterate over items

for (let w = W; w >= weights[i]; w--) {Iterate backwards over capacities

dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);Update dp[w] with max value including current item

⏱

Complexity

TimeO(n * W)

SpaceO(W)

We use a single dp array of size W+1 and update it for each item.

💡 This reduces memory usage significantly while maintaining time efficiency.

Interview Verdict: Accepted

This is the most space-efficient standard solution for 0/1 knapsack.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code the bottom-up tabulation or space optimized approach for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down Memoization	O(n * W)	O(n * W) memo + recursion stack	Possible for large n	Yes	Good to explain optimization over brute force
3. Bottom-Up Tabulation	O(n * W)	O(n * W)	No	Yes	Standard approach to code
4. Space Optimized Bottom-Up	O(n * W)	O(W)	No	No (without extra tracking)	Best for memory efficiency, mention if asked

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and learn how to explain your thought process clearly in interviews.

How to Present

Clarify the problem constraints and inputs.Explain the brute force approach and its inefficiency.Introduce memoization to optimize recursion.Present bottom-up tabulation as an iterative alternative.Finally, discuss space optimization to reduce memory.

Time Allocation

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

What the Interviewer Tests

Understanding of recursion and dynamic programming, ability to optimize naive solutions, and clarity in explaining tradeoffs.

Common Follow-ups

• What if item weights or values are very large? → Use value-based DP or approximation.
• Can you reconstruct the selected items? → Use a parent pointer or backtrack dp table.

💡 These follow-ups test deeper understanding and ability to extend the solution.

🔍

Pattern Recognition

When to Use

1) Problem involves selecting items with weights and values; 2) Capacity constraint; 3) Decision to include/exclude each item; 4) Maximize total value.

Signature Phrases

maximize total value without exceeding capacitychoose items to include or exclude

NOT This Pattern When

Fractional Knapsack - allows partial items and is solved greedily

Similar Problems

Subset Sum Problem - special case with values = weightsPartition Equal Subset Sum - checks if subset sums to half totalUnbounded Knapsack - allows unlimited copies of items

Practice

1. You are given an unlimited supply of coins of different denominations and a target amount. You need to find the number of distinct combinations of coins that sum up to the target amount, where the order of coins does not matter. Which algorithmic approach guarantees an efficient and correct solution for this problem?

easy

A. Greedy algorithm that picks the largest coin first until the amount is reached

B. Dynamic programming using a 1D array with nested loops iterating over coins and amounts in increasing order

C. Backtracking with pruning to explore all possible permutations of coins

D. Top-down recursion without memoization exploring all subsets of coins

Solution

1. Step 1: Understand problem constraints

   The problem requires counting combinations (order does not matter) of unlimited coins summing to amount.

2. Step 2: Identify suitable algorithm

   Greedy fails as it misses combinations; backtracking without memoization is exponential; permutations count order, not combinations. DP with 1D array iterating coins first ensures combinations are counted correctly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP approach counts combinations efficiently [OK]

Hint: Order coins outer loop to count combinations correctly [OK]

Common Mistakes:

• Using greedy approach
• Counting permutations instead of combinations
• Not using DP or memoization

2. The following code attempts to count the number of combinations to make change. Which line contains a subtle bug that causes it to count permutations instead of combinations?

medium

A. Line 5: inner loop iterating backwards over amounts

B. Line 4: outer loop over coins

C. Line 2: dp initialization

D. Line 6: updating dp[w] with dp[w - coin]

Solution

1. Step 1: Understand iteration order effect

   Iterating amounts backwards causes dp to count permutations, not combinations.

2. Step 2: Identify bug line

   Line 5 iterates w from amount down to coin, which breaks combination counting logic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration over amounts is required to count combinations correctly [OK]

Hint: Check direction of inner loop iteration [OK]

Common Mistakes:

• Using backward iteration in 1D dp
• Misplacing dp[0] initialization

3. What is the time complexity of the space-optimized bottom-up DP solution for Last Stone Weight II, where n is the number of stones and sum is the total weight of all stones?

medium

A. O(n + sum)

B. O(n^2)

C. O(n * sum * log n)

D. O(n * sum)

Solution

1. Step 1: Identify loops in the code

   Outer loop runs n times (for each stone), inner loop runs up to half the total sum (sum/2).

2. Step 2: Calculate total operations

   Each iteration updates dp array, so total operations ≈ n * (sum/2) -> O(n * sum).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP complexity depends on n and sum, not n squared or log factors [OK]

Hint: DP loops over stones and sums -> O(n * sum) [OK]

Common Mistakes:

• Confusing n with sum leading to O(n^2)
• Assuming logarithmic factor due to sorting
• Ignoring that dp array size depends on sum

4. Examine the following code snippet which attempts to solve the problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 7: zeros = s.count('0')

B. Line 10: for j in range(0, n - ones + 1):

C. Line 9: for i in range(0, m - zeros + 1): # iterating forwards

D. Line 11: dp[i + zeros][j + ones] = max(dp[i + zeros][j + ones], 1 + dp[i][j])

Solution

1. Step 1: Understand dp iteration direction

   To avoid counting the same string multiple times, dp must be updated backwards (from high to low indices).

2. Step 2: Identify bug in iteration

   Iterating forwards over i and j causes dp states to be reused within the same iteration, leading to overcounting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backward iteration is required for 0/1 knapsack variants [OK]

Hint: Forward iteration in 0/1 knapsack dp causes double counting [OK]

Common Mistakes:

• Forgetting to iterate dp backwards
• Miscounting zeros and ones

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