LeetCode 416: Partition Equal Subset Sum (0/1 Knapsack DP)

2026-03-16 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 416DPKnapsack

Today we solve LeetCode 416 - Partition Equal Subset Sum.

Source: https://leetcode.com/problems/partition-equal-subset-sum/

English

Problem Summary

Given an integer array nums, return true if you can split it into two subsets with equal sum.

Key Insight

If total sum is odd, answer is immediately false. Otherwise, the task becomes: can we pick some numbers whose sum is exactly target = total / 2? This is classic 0/1 knapsack subset-sum.

Brute Force and Limitations

Trying all subsets is O(2^n), which is too slow. DP tracks reachable sums and avoids recomputation.

Optimal Algorithm Steps

1) Compute total sum; if odd, return false.
2) Set target = total / 2 and initialize dp[0] = true.
3) For each number x, iterate s from target down to x.
4) Update dp[s] = dp[s] || dp[s - x].
5) Return dp[target].

Why Reverse Iteration?

Backward iteration ensures each number is used at most once. Forward iteration would allow reusing the same number in the same round, which breaks 0/1 constraints.

Complexity Analysis

Time: O(n * target).
Space: O(target).

Common Pitfalls

- Forgetting the odd-sum early return.
- Iterating DP forward (turns into unbounded knapsack behavior).
- Missing dp[0] = true initialization.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) sum += x;
        if ((sum & 1) == 1) return false;

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int x : nums) {
            for (int s = target; s >= x; s--) {
                dp[s] = dp[s] || dp[s - x];
            }
        }

        return dp[target];
    }
}

func canPartition(nums []int) bool {
    sum := 0
    for _, x := range nums {
        sum += x
    }
    if sum%2 == 1 {
        return false
    }

    target := sum / 2
    dp := make([]bool, target+1)
    dp[0] = true

    for _, x := range nums {
        for s := target; s >= x; s-- {
            dp[s] = dp[s] || dp[s-x]
        }
    }

    return dp[target]
}

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0) return false;

        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int x : nums) {
            for (int s = target; s >= x; --s) {
                dp[s] = dp[s] || dp[s - x];
            }
        }

        return dp[target];
    }
};

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        total = sum(nums)
        if total % 2 == 1:
            return False

        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True

        for x in nums:
            for s in range(target, x - 1, -1):
                dp[s] = dp[s] or dp[s - x]

        return dp[target]

var canPartition = function(nums) {
  let sum = 0;
  for (const x of nums) sum += x;
  if (sum % 2 === 1) return false;

  const target = sum / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

  for (const x of nums) {
    for (let s = target; s >= x; s--) {
      dp[s] = dp[s] || dp[s - x];
    }
  }

  return dp[target];
};

中文

题目概述

给定整数数组 nums，判断是否可以将其分成两个子集，使两个子集元素和相等。

核心思路

先看总和：若为奇数，不可能平分。若为偶数，则问题转化为：是否能从数组中选出若干元素，和恰好等于 target = sum / 2。这就是 0/1 背包中的子集和问题。

暴力解法与不足

直接枚举所有子集是 O(2^n)，数据稍大就超时。DP 用“可达和”状态避免重复搜索。

最优算法步骤

1）计算总和，若为奇数直接返回 false。
2）令 target = sum / 2，初始化 dp[0] = true。
3）遍历每个数 x，并让 s 从 target 递减到 x。
4）状态转移：dp[s] = dp[s] || dp[s - x]。
5）最终返回 dp[target]。

为什么必须倒序遍历？

倒序可以保证每个数字在本轮只被使用一次；若正序更新，会在同一轮重复使用当前数字，语义变成“完全背包”，结果错误。

复杂度分析

时间复杂度：O(n * target)。
空间复杂度：O(target)。

常见陷阱

- 忘记奇偶性剪枝。
- DP 循环方向写反。
- 忘记初始化 dp[0] = true。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) sum += x;
        if ((sum & 1) == 1) return false;

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int x : nums) {
            for (int s = target; s >= x; s--) {
                dp[s] = dp[s] || dp[s - x];
            }
        }

        return dp[target];
    }
}

func canPartition(nums []int) bool {
    sum := 0
    for _, x := range nums {
        sum += x
    }
    if sum%2 == 1 {
        return false
    }

    target := sum / 2
    dp := make([]bool, target+1)
    dp[0] = true

    for _, x := range nums {
        for s := target; s >= x; s-- {
            dp[s] = dp[s] || dp[s-x]
        }
    }

    return dp[target]
}

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0) return false;

        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int x : nums) {
            for (int s = target; s >= x; --s) {
                dp[s] = dp[s] || dp[s - x];
            }
        }

        return dp[target];
    }
};

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        total = sum(nums)
        if total % 2 == 1:
            return False

        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True

        for x in nums:
            for s in range(target, x - 1, -1):
                dp[s] = dp[s] or dp[s - x]

        return dp[target]

var canPartition = function(nums) {
  let sum = 0;
  for (const x of nums) sum += x;
  if (sum % 2 === 1) return false;

  const target = sum / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

  for (const x of nums) {
    for (let s = target; s >= x; s--) {
      dp[s] = dp[s] || dp[s - x];
    }
  }

  return dp[target];
};