Partition Equal Subset Sum (0/1 Knapsack)

mediumDynamic Programming+20 XPTime limit 2s

Can the array be split into two groups with equal sums? (Every element goes into exactly one group.)

Input:

line 1: n
line 2: n positive integers

Output: true or false.

Constraints: 1 ≤ n ≤ 200, 1 ≤ a[i] ≤ 100.

Think about it: if the total is odd → impossible. Otherwise ask: is there a subset with sum total / 2? That is 0/1 knapsack: can[s] |= can[s − x] for every element x, looping s downwards so each element is used at most once.

Sample input 1

4
1 5 11 5

Sample output 1

true

Sample input 2

4
1 2 3 5

Sample output 2

false

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…