Partition Equal Subset Sum

Solution

This problem is a variation of the $0/1$ Knapsack problem and subset sum decision problem, all of which are NP-complete and cannot be reduced to polynomial runtime, unless $P = NP$.

Let $n$ be the length of the array nums and $target$ be the half of total sum.

Iterative DP

See more at these two LeetCode posts in Chinese: 1 (opens new window) and 2 (opens new window).

$O(n \cdot target)$ Space

dp[i][j] represents whether there exists a way to select positive integers in nums[0..i] s.t. the sum is equal to $j$.

The base cases are:

• if no positive integer is selected, then $j = 0$. For all $0 \le i < n$, dp[i][0] = True
• when $i == 0$, only nums[0] can be selected. So dp[0][nums[0]] = True

For $i > 0$ and $j > 0$, dp[i][j] has the following two cases:

• if $j \ge$ nums[i], nums[i] can either be selected or not. dp[i][j] = True if either case is true:
  • if nums[i] not selected, dp[i][j] = dp[i-1][j]
  • if nums[i] selected, then dp[i][j] = dp[i-1][j-nums[i]]
• if $j <$ nums[i], then nums[i] cannot be selected: dp[i][j] = dp[i-1][j]

The state transition is:

if $j \ge$ nums[i], dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
else $j <$ nums[i], dp[i][j] = dp[i-1][j]

Return dp[n-1][target] as the final result.

Complexity

time: $O(n \cdot target)$
space: $O(n \cdot target)$

def canPartition(self, nums: List[int]) -> bool:
    # boilerplate
    n = len(nums)
    if n < 2:
        return False
    total = sum(nums)
    target = total // 2
    mx = max(nums)
    if total & 1 == 1 or mx > target:
        return False

    dp = [[False for _ in range(target+1)] for _ in range(n)]
    for i in range(n):
        dp[i][0] = True

    dp[0][nums[0]] = True
    for i in range(1, n):
        num = nums[i]
        for j in range(1, target+1):
            if j >= num:
                dp[i][j] = dp[i-1][j] or dp[i-1][j-num]
            else:
                dp[i][j] = dp[i-1][j]
        # early stop, pruning
        if dp[i][target]:
            return True
    return dp[n-1][target]

$O(target)$ Space

As dp in a iteration is only concerned with dp from last iteration, we only need a 1D array to store dp.

The state transition now is: dp[j] = dp[j] or dp[j - nums[i]]

Note that j is traversed in reverse order, b/c o.w. dp[j - nums[i]] is already updated, and no longer the value from previous iteration.

Complexity

time: $O(n \cdot target)$
space: $O(target)$

def canPartition(self, nums: List[int]) -> bool:
    # boilerplate
    n = len(nums)
    if n < 2:
        return False
    total = sum(nums)
    target = total // 2
    mx = max(nums)
    if total & 1 == 1 or mx > target:
        return False

    dp = [True] + [False for _ in range(target)]
    for num in nums:
        for j in range(target, num-1, -1):
            dp[j] |= dp[j - num]

    return dp[target]

Bit Manipulation

Turn dp into an int, or a bit array partitioned by each num.

Both time and space complexities are the best.

Complexity

time: $O(n \cdot target)$ (the $target$ is negligible depending on language implementations of bit array)
space: $O(target)$

def canPartition(self, nums: List[int]) -> bool:
    total = sum(nums)
    target = total // 2
    mx = max(nums)
    if total & 1 == 1 or mx > target:
        return False
    dp = 1
    for num in nums:
        dp |= dp << num
    return (dp >> target) & 1 == 1

DFS

Vanilla (TLE)

Complexity

time: $O(2^n)$
space: $O(n)$

def canPartition(self, nums: List[int]) -> bool:
    n = len(nums)
    total = sum(nums)
    target = total // 2
    mx = max(nums)
    if total & 1 == 1 or mx > target:
        return False

    def dfs(start, csum):
        if csum > target:
            return False
        if csum == target:
            return True
        for i in range(start, n):
            if dfs(i+1, csum+nums[i]):
                return True
        return False

    return dfs(0, 0)

Recursive DP w/ Memoization

Add csum to memo once visited.

Complexity

time: ???
space: $O(n)$

def canPartition(self, nums: List[int]) -> bool:
    n = len(nums)
    total = sum(nums)
    target = total // 2
    mx = max(nums)
    if total & 1 == 1 or mx > target:
        return False
    memo = set()

    def dfs(start, csum):
        if csum > target:
            return False
        if csum == target:
            return True
        if csum in memo:
            return False
        memo.add(csum)
        for i in range(start, n):
            if dfs(i+1, csum+nums[i]):
                return True
        return False

    return dfs(0, 0)