# Partition Equal Subset Sum

DPDFS

## # 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]

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)$ 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]

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(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

1
2
3
4
5
6
7
8
9
10

### # 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)

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)$

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
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