Subset Sum Problem

Problem

Given nonnegative integers and a target sum, determine whether some subset sums exactly to that target.

Examples

Example 1

Input: {"arr":[3,34,4,12,5,2],"sum":9}

Output: true

Explanation: A subset containing 4 and 5 adds up to 9.

Example 2

Input: {"arr":[3,34,4,12,5,2],"sum":30}

Output: false

Explanation: No subset of these numbers adds up to 30.

Input and output use JSON-compatible values. For linked-list and tree questions, arrays represent the node structure as described above. Your code should implement solve(input).

Write your solutionImplement solve(input). Your draft is saved in this browser.

Compiler

How to solve Subset Sum Problem

We can solve Subset Sum with dynamic programming. Start with sum 0 as achievable (the empty subset). For each array number, add new achievable totals without reusing the same number. Finally, check whether the target is reachable.

Time and space complexity

O(n × target) pseudo-polynomial time and O(target) space.

Practise and improve

Choose JavaScript, TypeScript or Python, complete the starter code, then select Run Tests. Request a hint when you need guidance, or choose View solution and confirm if you would like to study the reference implementation.