Partition Equal Subset Sum

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

# Solution

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

Let nn be the length of the array nums and targettarget 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(ntarget)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 jj.

The base cases are:

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

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

  • if jj \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<j < nums[i], then nums[i] cannot be selected: dp[i][j] = dp[i-1][j]

The state transition is:

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

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

Complexity

time: O(ntarget)O(n \cdot target)
space: O(ntarget)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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# O(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(ntarget)O(n \cdot target)
space: O(target)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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 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(ntarget)O(n \cdot target) (the targettarget is negligible depending on language implementations of bit array)
space: O(target)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
1
2
3
4
5
6
7
8
9
10

# DFS

# Vanilla (TLE)

Complexity

time: O(2n)O(2^n)
space: O(n)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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Recursive DP w/ Memoization

Add csum to memo once visited.

Complexity

time: ???
space: O(n)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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23