Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogleFacebook

Subset Sum

Choose your preparation mode4 modes available
📋
Problem

Imagine you have a collection of coins and want to know if you can pick some to exactly pay a certain amount without breaking any coin.

Given an array of positive integers nums and a target sum S, determine if there exists a subset of nums whose sum is exactly S. Return true if such a subset exists, otherwise false.

1 ≤ n ≤ 10^51 ≤ nums[i] ≤ 10^41 ≤ S ≤ 10^6
Edge cases: Empty array with S=0 → true (empty subset)Empty array with S>0 → false (no elements to sum)All elements greater than S → false
</>
IDE
def subset_sum(nums: list[int], S: int) -> bool:public boolean subsetSum(int[] nums, int S)bool subsetSum(vector<int>& nums, int S)function subsetSum(nums, S)
def subset_sum(nums, S):
    # Write your solution here
    pass
class Solution {
    public boolean subsetSum(int[] nums, int S) {
        // Write your solution here
        return false;
    }
}
#include <vector>
using namespace std;

bool subsetSum(vector<int>& nums, int S) {
    // Write your solution here
    return false;
}
function subsetSum(nums, S) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: falseDP does not correctly include subsets that sum to target; missing inclusion condition.✅ Update dp[i][s] = dp[i-1][s] or dp[i-1][s - nums[i-1]] if s >= nums[i-1].
Wrong: trueIncorrectly returns true for empty array with positive sum due to missing base case initialization.✅ Initialize dp[0][s] = false for all s > 0 and dp[0][0] = true.
Wrong: trueFails 0/1 constraint by allowing multiple uses of same element (unbounded knapsack).✅ Iterate sums backward when updating dp to prevent reuse of elements.
Wrong: falseGreedy approach picks largest elements first, missing valid subsets.✅ Use full DP to consider all subsets, not greedy selection.
Wrong: TLEExponential or unoptimized DP solution with large n and S.✅ Implement bottom-up DP with pruning or space optimization.
✓
Test Cases
t1_01basic
Input{"nums":[3,34,4,12,5,2],"S":9}
Expectedtrue

Subset [4, 5] sums to 9.

t1_02basic
Input{"nums":[1,2,3,7],"S":6}
Expectedtrue

Subset [1, 2, 3] sums to 6.

t2_01edge
Input{"nums":[],"S":0}
Expectedtrue

Empty subset sums to 0 by definition.

t2_02edge
Input{"nums":[],"S":5}
Expectedfalse

No elements to sum to a positive target.

t2_03edge
Input{"nums":[10,11,12],"S":9}
Expectedfalse

All elements greater than target sum, no subset possible.

t3_01corner
Input{"nums":[1,2,3,4,5],"S":10}
Expectedtrue

Subset [1, 2, 3, 4] sums to 10; tests greedy trap.

t3_02corner
Input{"nums":[2,2,2],"S":4}
Expectedtrue

Subset [2, 2] sums to 4; tests 0/1 vs unbounded confusion.

t3_03corner
Input{"nums":[1,3,5],"S":4}
Expectedtrue

Tests off-by-one errors in DP indexing.

t4_01performance
Input{"nums":[10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987,9986,9985,9984,9983,9982,9981,9980,9979,9978,9977,9976,9975,9974,9973,9972,9971,9970,9969,9968,9967,9966,9965,9964,9963,9962,9961,9960,9959,9958,9957,9956,9955,9954,9953,9952,9951,9950,9949,9948,9947,9946,9945,9944,9943,9942,9941,9940,9939,9938,9937,9936,9935,9934,9933,9932,9931,9930,9929,9928,9927,9926,9925,9924,9923,9922,9921,9920,9919,9918,9917,9916,9915,9914,9913,9912,9911,9910,9909,9908,9907,9906,9905,9904,9903,9902,9901],"S":1000000}
⏱ Performance - must finish in 2000ms

Large input with n=100 and large S=1,000,000 to test O(n*S) DP performance within 2 seconds.

Practice

(1/5)
1. Given the following code, what is the output when coins = [1, 2, 5] and amount = 5?
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]

coins = [1, 2, 5]
amount = 5
print(count_ways_space_opt(coins, amount))
easy
A. 4
B. 7
C. 5
D. 6

Solution

  1. Step 1: Trace dp array updates for each coin

    Start dp = [1,0,0,0,0,0]. After coin=1, dp = [1,1,1,1,1,1]. After coin=2, dp = [1,1,2,2,3,3]. After coin=5, dp = [1,1,2,2,3,6].
  2. Step 2: Confirm dp[5] value

    dp[5] = 6, representing 6 ways to make amount 5 with coins [1,2,5].
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Manual dp tracing matches output 6 [OK]
Hint: DP accumulates counts incrementally per coin [OK]
Common Mistakes:
  • Off-by-one in dp indexing
  • Miscounting after last coin iteration
  • Confusing permutations with combinations
2. What is the time complexity of the optimal job scheduling algorithm that sorts jobs by end time and uses binary search with a DP array of size n?
medium
A. O(n log W) where W is the maximum end time
B. O(n^2) due to nested loops over all jobs
C. O(n) because each job is processed once
D. O(n log n) due to sorting and binary searches for each job

Solution

  1. Step 1: Identify sorting cost

    Sorting n jobs by end time costs O(n log n).
  2. Step 2: Analyze DP loop with binary search

    For each job, binary search among ends array costs O(log n), repeated n times -> O(n log n).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Sorting + n binary searches dominate; no nested O(n^2) loops [OK]
Hint: Sorting + binary search per job -> O(n log n) [OK]
Common Mistakes:
  • Assuming O(n^2) due to DP
  • Ignoring binary search cost
  • Confusing max end time W with input size n
3. The following code attempts to solve the job scheduling problem optimally. Which line contains a subtle bug that can cause incorrect results?
medium
A. Line 11: Using bisect_right to find compatible job index
B. Line 7: Creating ends array from job end times
C. Line 4: Sorting jobs by start time instead of end time
D. Line 14: Calculating dp[i] as max of take and skip

Solution

  1. Step 1: Identify sorting criteria

    Jobs must be sorted by end time for binary search on ends array to work correctly.
  2. Step 2: Check sorting line

    Line 4 sorts by start time, breaking DP dependencies and binary search correctness.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sorting by start time causes incorrect compatible job lookups and suboptimal profits [OK]
Hint: Sort jobs by end time, not start time [OK]
Common Mistakes:
  • Sorting by start time
  • Incorrect binary search bounds
  • Ignoring dp base cases
4. Suppose the problem changes so that you can use each item an unlimited number of times (unbounded knapsack). Which modification to the space-optimized bottom-up DP code correctly solves this variant?
hard
A. Change the inner loop to iterate forwards from weights[i] up to W.
B. Add memoization to the recursive solution to avoid recomputation.
C. Change the inner loop to iterate backwards from W down to weights[i].
D. Use a greedy approach selecting items with the highest value-to-weight ratio repeatedly.

Solution

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

    In unbounded knapsack, items can be chosen multiple times, so dp[w] can be updated using dp[w - weights[i]] from the same iteration.
  2. Step 2: Identify correct iteration order

    Iterating forwards from weights[i] to W allows reuse of updated dp values within the same iteration, enabling multiple counts of the same item.
  3. Step 3: Why other options fail

    Backward iteration prevents multiple usage in one iteration (wrong for unbounded). Memoization helps but is not the direct fix. Greedy fails for 0/1 and unbounded knapsack except fractional case.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Forward iteration enables unlimited item reuse [OK]
Hint: Unbounded knapsack requires forward iteration in dp updates [OK]
Common Mistakes:
  • Using backward iteration from 0/1 knapsack causes incorrect results.
5. Suppose the problem is modified so that each string can be chosen multiple times (unbounded usage). Which change to the dynamic programming approach correctly adapts the solution?
hard
A. Iterate dp array forwards to allow multiple counts of the same string
B. Iterate dp array backwards as before to avoid counting duplicates
C. Use recursion without memoization to handle repeated choices
D. Increase dp dimensions to track usage count of each string

Solution

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

    Unbounded knapsack allows multiple uses of the same item, so dp updates must allow reuse within the same iteration.
  2. Step 2: Adjust dp iteration order

    Iterating dp forwards enables using updated states multiple times, correctly counting repeated strings.
  3. Step 3: Confirm correctness

    Backward iteration prevents reuse in the same iteration, which is incorrect for unbounded usage.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Forward iteration enables multiple item usage [OK]
Hint: Unbounded knapsack uses forward dp iteration [OK]
Common Mistakes:
  • Continuing backward iteration from 0/1 knapsack
  • Adding extra dp dimensions unnecessarily
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