Practice › Dynamic Programming
Partition Equal Subset Sum
Medium · Dynamic Programming · Asked at Amazon, Microsoft, Adobe, Meta
Print YES if the array can be split into two subsets with equal sums, otherwise NO.
Input
First line: n. Second line: n positive integers.
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 200
- 1 ≤ a[i] ≤ 100
Subset-sum DP for target = total / 2 (impossible if the total is odd).
Example 1
Input
4 1 5 11 5
Output
YES
Example 2
Input
4 1 2 3 5
Output
NO
Hints
- Both halves must sum to total / 2 — an odd total makes it impossible.
- Subset sum: can[s] = can some subset reach exactly s? For each number x, loop s downwards: can[s] |= can[s − x].
Approach
If the total is odd, answer NO. Otherwise look for a subset summing to target = total / 2. Keep a boolean array can[0..target] with can[0] = true. For each number x, update s from target down to x: can[s] = can[s] || can[s − x]. Going downwards uses each number at most once, as in 0/1 knapsack. The answer is can[target]. The Python version stores the same table as bits of one big integer, which is much faster.
Complexity: O(n · total) time · O(total) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
int total = 0;
for (auto &x : a) {
cin >> x;
total += x;
}
if (total % 2 == 1) {
cout << "NO\n";
return 0;
}
int target = total / 2;
vector<bool> can(target + 1, false);
can[0] = true;
for (int x : a)
for (int s = target; s >= x; s--)
if (can[s - x]) can[s] = true;
cout << (can[target] ? "YES" : "NO") << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1 : data[0] + 1]
total = sum(a)
if total % 2:
print("NO")
else:
target = total // 2
reachable = 1 # bit s is set when some subset sums to s
for x in a:
reachable |= reachable << x
print("YES" if reachable >> target & 1 else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
int total = 0;
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
total += a[i];
}
if (total % 2 == 1) {
System.out.println("NO");
return;
}
int target = total / 2;
boolean[] can = new boolean[target + 1];
can[0] = true;
for (int x : a)
for (int s = target; s >= x; s--)
if (can[s - x]) can[s] = true;
System.out.println(can[target] ? "YES" : "NO");
}
}Solve Partition Equal Subset Sum online · All practice problems