Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Both halves must sum to total / 2 — an odd total makes it impossible.
  2. 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