[Solved] Suppose the subset sum problem is modified so that each number can be chosen multiple times (unbounded). Which modification to the space-optimized DP code correctly solves this variant? | Dynamic Programming: Knapsack

Dynamic Programming: Knapsack - Subset Sum

Suppose the subset sum problem is modified so that each number can be chosen multiple times (unbounded). Which modification to the space-optimized DP code correctly solves this variant?

AChange the inner loop to iterate forwards from num to S, allowing reuse of the same number multiple times.

BKeep the inner loop iterating backwards from S to num, as in the 0/1 subset sum problem.

CUse a recursive brute force approach without memoization to handle multiple uses.

DSort the input array and apply a greedy approach picking largest numbers first.

Step-by-Step Solution

Solution:

Step 1: Understand difference between 0/1 and unbounded knapsack
In unbounded knapsack, items can be reused multiple times, so dp updates must allow reuse within the same iteration.
Step 2: Modify iteration direction
Iterating forwards allows dp[w] to use dp[w - num] updated in the same iteration, enabling multiple uses of num.
Step 3: Confirm correctness
Backward iteration prevents reuse in the same iteration, which is incorrect for unbounded variant.
Final Answer:
Option A -> Option A
Quick Check:
Forward iteration enables multiple uses -> correct for unbounded knapsack [OK]

Quick Trick: Unbounded knapsack requires forward iteration to allow reuse [OK]

Common Mistakes:

MISTAKES

Using backward iteration from 0/1 knapsack
Trying greedy or brute force without memoization

Trap Explanation:

PITFALL

Backward iteration looks correct but forbids multiple uses, breaking unbounded logic.

Interviewer Note:

CONTEXT

Tests candidate's ability to adapt DP iteration for problem variants.

Master "Subset Sum" in Dynamic Programming: Knapsack

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Dynamic Programming: Knapsack Quizzes

Suppose the subset sum problem is modified so that each number can be chosen multiple times (unbounded). Which modification to the space-optimized DP code correctly solves this variant?

Step 1: Understand difference between 0/1 and unbounded knapsack

Step 2: Modify iteration direction

Step 3: Confirm correctness

Final Answer:

Quick Check:

Want More Practice?