Full lesson preview

Decide if a subset sum is possible

Determine whether any subset of numbers sums exactly to a target using dynamic programming.

Python practice16 minDynamic ProgrammingIntermediateLast updated March 29, 2026

Problem statement

Given a list of nonnegative integers and a target sum, determine whether there exists a subset of the numbers that adds up exactly to the target. Return True if such a subset exists, otherwise return False.

Task

Use a DP (tabulation or bitset) approach to decide whether a subset of given integers sums to the target.

Examples

Classic example

Input

nums = [3, 34, 4, 12, 5, 2], target = 9

Output

True

Subset {4,5} sums to 9.

Input format

Function subset_sum(nums: List[int], target: int)

Output format

Return True if a subset sums to target, otherwise False.

Constraints

0 <= len(nums) <= 1000. 0 <= nums[i] <= 10^5. 0 <= target <= 10^5. Aim for O(n * target) time and O(target) space or better.

Samples

Sample 1

Input

subset_sum([], 0)

Output

True

Empty subset sums to 0.