81. Partition Equal Subset Sum · DSA Practice

Can nums be split into two subsets with equal sums?

Example 1

Input: nums = [1,5,11,5]

Output: true

Explanation: [1, 5, 5] and [11].

Example 2

Input: nums = [1,2,3,5]

Output: false

Hint 1

If the total is odd, the answer is no.

Hint 2

Otherwise: is there a subset summing to total / 2? That is 0/1 knapsack.

Dynamic ProgrammingKnapsack

Approach 1: Subset-sum DP

Boolean knapsack over sums up to total/2.

⏱ Time O(n · S)💾 Space O(S)

Approach 2: Bitset ✅

Shift-or a bitset for each number.

⏱ Time O(n · S / 64)💾 Space O(S)

Reference solution for Bitset (time O(n · S / 64), space O(S)). Each solution passes every test in all four languages.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        reach = [True] + [False] * target       # reach[s]: some subset sums to s
        for x in nums:
            for s in range(target, x - 1, -1):  # 0/1 knapsack: loop backwards
                reach[s] = reach[s] or reach[s - x]
        return reach[target]

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 != 0) return false;
        int target = total / 2;
        boolean[] reach = new boolean[target + 1];
        reach[0] = true;
        for (int x : nums)
            for (int s = target; s >= x; s--) reach[s] = reach[s] || reach[s - x];
        return reach[target];
    }
}

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if (total % 2) return false;
        int target = total / 2;
        vector<bool> reach(target + 1, false);
        reach[0] = true;
        for (int x : nums)
            for (int s = target; s >= x; s--) reach[s] = reach[s] || reach[s - x];
        return reach[target];
    }
};

function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2) return false;
  const target = total / 2, reach = new Array(target + 1).fill(false);
  reach[0] = true;
  for (const x of nums)
    for (let s = target; s >= x; s--) reach[s] = reach[s] || reach[s - x];
  return reach[target];
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Dynamic Programming (2-D).