Subset Sum

📋

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
}

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

Focus on handling empty and minimal inputs correctly.

Beware of common algorithmic traps like greedy and unbounded usage.

Prepare for performance challenges with large inputs.

t1_01basic

Input{"nums":[3,34,4,12,5,2],"S":9}

Expectedtrue

⏱ Performance - must finish in 2000ms

Subset [4, 5] sums to 9.

💡 Think about whether you can include or exclude each number to reach the target sum.

💡 Use dynamic programming to track which sums are achievable with subsets of the array.

💡 Build a boolean DP table where dp[i][s] indicates if sum s is achievable using first i elements.

Why it failed: Failed basic case: likely missing the condition to include or exclude elements properly in DP. Fix by ensuring dp[i][s] = dp[i-1][s] or dp[i-1][s - nums[i-1]] if s >= nums[i-1].

✓ Correctly identifies achievable sums using subsets.

t1_02basic

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

Expectedtrue

⏱ Performance - must finish in 2000ms

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

💡 Try to find a subset that sums exactly to the target by including or excluding elements.

💡 Check if dp[i][s] can be true by either excluding or including nums[i-1].

💡 Update dp table accordingly: dp[i][s] = dp[i-1][s] or dp[i-1][s - nums[i-1]] if s >= nums[i-1].

Why it failed: Incorrect output: likely not handling subset sums correctly for smaller targets. Fix by properly updating DP states for each element and sum.

✓ DP correctly tracks achievable sums for given input.

t2_01edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty subset sums to 0 by definition.

💡 Consider the base case where no elements are chosen and target sum is zero.

💡 DP initialization should mark dp[0][0] as true since empty subset sums to zero.

💡 Ensure your code returns true when target sum is zero regardless of array content.

Why it failed: Fails empty input with zero sum: likely missing base case dp[0][0] = true. Fix by initializing dp[0][0] = true.

✓ Correctly handles empty array with zero target sum.

t2_02edge

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

Expectedfalse

⏱ Performance - must finish in 2000ms

No elements to sum to a positive target.

💡 If array is empty and target sum is positive, no subset can achieve it.

💡 DP should reflect that no sums > 0 are achievable with zero elements.

💡 Check that dp[0][s] is false for all s > 0.

Why it failed: Incorrectly returns true for empty array with positive sum: fix by ensuring dp[0][s] = false for s > 0.

✓ Correctly returns false when no elements exist for positive sum.

t2_03edge

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

Expectedfalse

⏱ Performance - must finish in 2000ms

All elements greater than target sum, no subset possible.

💡 If all elements are greater than target sum, no subset can sum to target.

💡 DP should never mark sums less than smallest element as achievable except zero.

💡 Check that your code does not incorrectly include elements that exceed the target.

Why it failed: Fails to exclude elements larger than target sum: fix by skipping elements where nums[i] > current sum in DP update.

✓ Correctly excludes elements larger than target sum.

t3_01corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

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

💡 Greedy approach picking largest elements first may fail here.

💡 DP must consider all subsets, not just largest elements.

💡 Use full DP to check all combinations rather than greedy selection.

Why it failed: Fails greedy trap: returns false by picking largest elements first. Fix by implementing full DP subset sum, not greedy.

✓ Correctly handles cases where greedy fails.

t3_02corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

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

💡 Ensure each element is used at most once (0/1 knapsack).

💡 DP state should not allow multiple uses of the same element.

💡 Update dp in reverse order of sums to prevent reuse of elements.

Why it failed: Fails 0/1 constraint: returns true for sums requiring multiple uses of same element. Fix by iterating sums backward in DP.

✓ Correctly enforces 0/1 usage of elements.

t3_03corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in DP indexing.

💡 Check DP indexing carefully to avoid off-by-one errors.

💡 Ensure dp array size and indices match sums from 0 to S inclusive.

💡 Verify base cases and transitions handle boundaries correctly.

Why it failed: Off-by-one error causes incorrect dp indexing and wrong result. Fix by correctly indexing dp arrays from 0 to S inclusive.

✓ DP indexing correctly implemented.

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}

Expectednull

⏱ 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.

💡 DP solution has O(n*S) time complexity; large S causes timeouts.

💡 Consider space and time optimizations or pruning techniques.

💡 Brute force exponential solutions will definitely time out here.

Why it failed: TLE due to O(n*S) complexity with large S and n=100. Fix by using optimized DP or pruning.

✓ Efficient DP or pruning techniques handle large input within time.

Practice

1. You are given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity. You want to maximize the total value of items placed in the knapsack without exceeding its capacity. Which algorithmic approach guarantees finding the optimal solution for this problem?

easy

A. A greedy algorithm that picks items with the highest value-to-weight ratio first.

B. Dynamic programming that considers including or excluding each item for every capacity up to the maximum.

C. A simple recursive approach without memoization that tries all subsets of items.

D. A breadth-first search exploring all possible combinations of items.

Solution

1. Step 1: Understand problem constraints and overlapping subproblems

   The problem requires maximizing value without exceeding capacity, which is a classic optimization problem with overlapping subproblems suitable for dynamic programming.

2. Step 2: Identify algorithmic approach that guarantees optimality

   Greedy algorithms fail because picking locally optimal items (highest value/weight) does not guarantee global optimum. Exhaustive search is correct but inefficient. Dynamic programming systematically explores all item inclusion/exclusion states with memoization, ensuring optimality.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP solves 0/1 Knapsack optimally by exploring all states [OK]

Hint: DP with inclusion/exclusion ensures optimal solution [OK]

Common Mistakes:

• Greedy approach works for fractional knapsack, not 0/1 knapsack.

2. 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

3. The following code attempts to implement the space-optimized 0/1 Knapsack solution. Identify the line that contains a subtle bug that can cause incorrect results.

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

medium

A. Line 5: Inner loop iterating forwards over weights.

B. Line 4: Outer loop iterating over items.

C. Line 2: Initializing dp array with zeros.

D. Line 6: Updating dp[w] with max of current and new value.

Solution

1. Step 1: Analyze iteration order in inner loop

   The inner loop iterates forwards from weights[i] to W, which causes the current item to be counted multiple times in the same iteration, violating 0/1 knapsack constraints.

2. Step 2: Correct iteration direction

   Iterating backwards (from W down to weights[i]) ensures each item is only counted once per capacity, preserving correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration causes overcounting items [OK]

Hint: Inner loop must iterate backwards to avoid overcounting [OK]

Common Mistakes:

• Iterating forwards in dp array updates for 0/1 knapsack.

4. What is the time complexity of the bottom-up dynamic programming solution for the integer break problem shown below?

def integer_break(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]

medium

A. O(n log n) time

B. O(n) time

C. O(2^n) time

D. O(n^2) time

Solution

1. Step 1: Identify loops

   Outer loop runs from 2 to n (≈ n iterations). Inner loop runs from 1 to i (up to n iterations).

2. Step 2: Calculate total operations

   Nested loops yield roughly 1 + 2 + ... + n ≈ n(n+1)/2 = O(n^2) operations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Double nested loops with linear bounds -> quadratic time [OK]

Hint: Nested loops with linear bounds usually mean O(n²) [OK]

Common Mistakes:

• Confusing with O(n) by ignoring inner loop
• Thinking recursion stack adds exponential time here

5. Suppose the problem is modified so that each number in the input array can be used multiple times to form the subsets. Which change to the DP approach correctly solves this variant?

hard

A. Keep the same code but iterate the dp array backwards to avoid reuse of elements

B. Change the inner loop to iterate forwards from num to target to allow multiple uses of the same element

C. Use recursion without memoization to explore all combinations with repeats

D. Double the dp array size to track counts of each element used

Solution

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

   Allowing multiple uses means the problem becomes unbounded knapsack, which requires forward iteration over dp array.

2. Step 2: Identify correct dp iteration direction

   Iterating forwards from num to target allows dp[w] to build upon dp[w - num] updated in the same iteration, enabling multiple uses.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backward iteration prevents multiple uses; forward iteration enables them [OK]

Hint: Forward dp iteration enables multiple uses of elements [OK]

Common Mistakes:

• Using backward iteration from 0/1 knapsack
• Ignoring iteration direction for repeats