Subset Sum Exists

Determine if any subset of numbers sums exactly to a target value.

subset sum dynamic programming knapsack boolean dp

Write a function `subset_sum_exists(nums, target)` that receives a list of positive integers `nums` and a non-negative integer `target`. The function must return `True` if there exists a subset (any non-empty selection of elements, but empty subset is allowed only if target == 0) whose sum equals `target`, and `False` otherwise. You may use each number at most once. The order of elements does not matter.

Implement your solution efficiently. The naive enumeration of all subsets is acceptable for small inputs, but you are expected to handle reasonably larger inputs using dynamic programming or another efficient approach.

Constraints

- 0 <= len(nums) <= 200
- 1 <= each num <= 1000
- 0 <= target <= 10000
- Your solution should run in O(n * target) time or better, where n = len(nums).
- Do not import any libraries beyond the Python standard library (if needed). Return a boolean.

Example

>>> subset_sum_exists([3, 34, 4, 12, 5, 2], 9)
True
>>> subset_sum_exists([3, 34, 4, 12, 5, 2], 30)
False
>>> subset_sum_exists([1, 2, 3], 0)
True
>>> subset_sum_exists([], 5)
False

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Consider using a boolean DP array where dp[s] indicates whether sum s is achievable.

Initialize dp[0] = True and iterate over each number, updating achievable sums from high to low to avoid reusing the same element.

If target is larger than the sum of all numbers, you can immediately return False.

Think about edge cases: empty list, target = 0, or when target is exactly one of the numbers.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.