Approach: 0/1 knapsack on sum/2

def canPartition(nums):
    total = sum(nums)
    if total % 2: return False
    t = total // 2
    dp = [False]*(t+1)
    dp[0] = True
    for x in nums:
        for j in range(t, x-1, -1):
            dp[j] = dp[j] or dp[j-x]
    return dp[t]

Complexity: O(n * sum) time, O(sum) space.

Full Solution — all languages

class Solution:
    def canPartition(self, nums):
        total = sum(nums)
        if total % 2:
            return False
        t = total // 2
        dp = [False] * (t + 1)
        dp[0] = True
        for x in nums:
            for j in range(t, x - 1, -1):
                if dp[j - x]:
                    dp[j] = True
        return dp[t]

import java.util.*;
class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 == 1) return false;
        int t = total / 2;
        boolean[] dp = new boolean[t + 1];
        dp[0] = true;
        for (int x : nums) for (int j = t; j >= x; j--) if (dp[j - x]) dp[j] = true;
        return dp[t];
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: bool canPartition(vector<int>& nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 == 1) return false;
        int t = total / 2;
        vector<bool> dp(t + 1, false);
        dp[0] = true;
        for (int x : nums) for (int j = t; j >= x; j--) if (dp[j - x]) dp[j] = true;
        return dp[t];
    }
};

/**
 * @param {number[]} nums
 * @return {boolean}
 */ var canPartition = function(nums) {
    let total = 0;
    for (const x of nums) total += x;
    if (total % 2 === 1) return false;
    const t = total / 2;
    const dp = new Array(t + 1).fill(false);
    dp[0] = true;
    for (const x of nums) for (let j = t; j >= x; j--) if (dp[j - x]) dp[j] = true;
    return dp[t];
};

Partition Equal Subset Sum

Example 1

Example 2

Constraints