LC 416 - Partition Equal Subset Sum
Question
Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.
Example 1:
1
2
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
1
2
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= 100
Links
Question here and solution here
Solution
concept
Note that odd sum will fail so we should rule out this case. Note after that (i.e. it is even sum) we just need to find one set of numbers that can sum to sum//2 and the other half is guaranteed.
top down memoization
use DFS and track target (or remainder) at index i, which tell us if we arrive at index i with remainder target, can we find all the numbers that satisfied the remainder with remaining numbers (from index i onwards).
bottom up solution
check if any of the subarray sum is equal to the half of the total sum -> target sum, which means the rest of the array is also equal to target sum DP from the end of the array (bottom up DP) we maintan a list of all possible sum of subarray at index i (which means all possible sum value in sub array nums[i:]) in each iteration, we
- add the current element to the dp list, since this num alone can be a valid sum by itself
- retain the previous sum value in dp list since they are still valid sum value (from the previous subarray)
- add the current element to the previous sum value in dp list (except the last value which is the curr value), since the sum of the previous subarray + the current element can be a valid sum value
If the target is in the dp list, return True, otherwise return False
code
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
class Solution:
"""
brute force
TLE
"""
def canPartition(self, nums: List[int]) -> bool:
s = sum(nums)
if s%2: # odd sum
return False
def dfs(i, target): # or rather, remainder
if i >= len(nums):
return target == 0
if target < 0:
return False
return dfs(i+1, target) or dfs(i+1, target - nums[i])
return dfs(0, s//2)
class Solution:
"""
top down (memoization)
"""
def canPartition(self, nums: List[int]) -> bool:
s = sum(nums)
if s%2: # odd sum
return False
cache = {} # (i, target): T/F
def dfs(i, target): # or rather, remainder
if i >= len(nums):
cache[(i, target)] = target == 0
return cache[(i, target)]
if (i, target) in cache:
return cache[(i, target)]
if target < 0:
cache[(i, target)] = False
return cache[(i, target)]
cache[(i, target)] = dfs(i+1, target) or dfs(i+1, target - nums[i])
return cache[(i, target)]
return dfs(0, s//2)
class NeetSolution:
"""
top down (memoizatation)
"""
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
n = len(nums)
# each index is an array stores all possible targets if can achieve or not
memo = [[-1] * (target + 1) for _ in range(n + 1)]
def dfs(i, target):
if target == 0:
return True
if i >= n or target < 0:
return False
if memo[i][target] != -1:
return memo[i][target]
memo[i][target] = (dfs(i + 1, target) or
dfs(i + 1, target - nums[i]))
return memo[i][target]
return dfs(0, target)
class Solution:
"""
another top down solution
"""
def canPartition(self, nums: List[int]) -> bool:
if sum(nums)%2:
return False
else:
target = sum(nums)//2
cache = {}
def dfs(i, cur_sum):
if (i, cur_sum) in cache:
return cache[(i, cur_sum)]
if cur_sum == target:
return True
if cur_sum >= target:
return False
if i >= len(nums):
return False
cur_sum += nums[i]
if dfs(i + 1, cur_sum):
return True
cur_sum -= nums[i]
if dfs(i + 1, cur_sum):
return True
cache[(i, cur_sum)] = False
return cache[(i, cur_sum)]
return dfs(0,0)
class Solution:
"""
bottom up
time complexity: O(2^n), n is the length of the nums
"""
def canPartition(self, nums: List[int]) -> bool:
dp = []
# if total sum is odd then it is impossible to partition the array into two equal sum subarray, since all elements are int
if sum(nums)%2: # odd
return False
else:
target = sum(nums)//2
for i in range(len(nums)-1, -1, -1):
# add the current element to the dp list
dp.append(nums[i])
# retain the previous sum value in dp list
# add curr to all previous sum value in dp list, except the last value since it is the curr value
for j in range(len(dp)-1):
dp.append(dp[j] + nums[i])
if target in dp:
return True
# deduplicate the dp list since we can have duplicate in nums, we just need unique possible/valid sum value
# without this we will have memory error on LC
dp = list(set(dp))
return False
class NeetSolution:
def canPartition(self, nums: List[int]) -> bool:
if sum(nums) % 2:
return False
# NeetCode used a set with initial value 0
# so subsequent if curr num + all existing value in set will have a curr value (0 + curr = curr)
# so no need to append curr and also when adding curr to all existing value in set, we don't need to code to avoid last value
dp = set()
dp.add(0)
target = sum(nums) // 2
for i in range(len(nums) - 1, -1, -1):
# we cannot update dp while iterating over it, so we need to create a new set
nextDP = set()
for t in dp:
if (t + nums[i]) == target:
return True
nextDP.add(t + nums[i])
# this is just to prevseve whatever value we have in dp into the nextDP
# you could also clone it first
nextDP.add(t)
dp = nextDP
return False
Complexity
time: $O(n)$
space: $O(n)$