This can also be solved using two-pointers
# WRITE YOUR BRILLIANT CODE HERE
n = len(nums)
l,r = 0, n-1
nums.sort()
l_sum, r_sum=nums[l], nums[r]
while l < r:
if l_sum < r_sum:
l+=1
l_sum+=nums[l]
elif l_sum > r_sum:
r-=1
r_sum+=nums[r]
else:
return True
return False
Another way to dedupe in DFS is using search-space deduping. See Backtracking → Subsets for details.
Instead of tracking used indices, we can pick next indices as candidates to visit only unique subsets.
Is Mem working?
We are only checking for current sum has been already explored. But used array may not be same for previously explored current sum. Don’t we need to check current sum same and used array same before looking up mem value?
this will fail the following test: 1 6 6 11
why do we need the used array? would this also work?
def can_partition(nums: List[int]) → bool:
target = sum(nums) // 2
def dfs(i, cursum):
if cursum == target:
return True
for ni, num in enumerate(nums[i::]):
if cursum + num <= target:
return dfs(ni +1, cursum + num)
return False
return dfs(0,0)
we can modify the prefix sum to do it
if(ps == target || map.containsKey(ps-target)){
return true;
}
we can modify the prefix sum to do it
if(ps == target || map.containsKey(ps-target)){
return true;
}
My dfs solution works but got TLE on leetcode. Could anyone explain the DP solution more clearly? I’ve found this one is tough to understand.
Check this out: https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
Ok, thanks, found a proper way to do DP after watching this https://www.youtube.com/watch?v=fWX9xDmIzRI&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY&index=15
Sharing all 3 solutions, I’ve found if I start from brute force, DP will make more sense to me
# # S1 - Top-down Recursion, TLE, TC = 2**N, SC = N
# class Solution:
# def canPartition(self, nums: List[int]) -> bool:
# total = sum(nums)
# if total % 2 != 0:
# return False
# half = total // 2
# def f(idx, nums, target) -> bool:
# if idx == 0:
# if nums[idx] == target:
# return True
# return False
# if target == 0:
# return True
# # Take
# take = False
# if target >= nums[idx-1]:
# take = f(idx-1, nums, target-nums[idx])
# # Not take
# not_take = f(idx-1, nums, target)
# return take or not_take
# return f(len(nums)-1, nums, half)
# # S2 - Top-down Recursion with Memoiation, TC = 2**N, SC = N + N*(SUM(nums))
# class Solution:
# def canPartition(self, nums: List[int]) -> bool:
# total = sum(nums)
# if total % 2 != 0:
# return False
# half = total // 2
# def f(idx, nums, target, dp) -> bool:
# if idx == 0:
# if nums[idx] == target:
# return True
# return False
# if target == 0:
# return True
# if dp[idx][target] != -1:
# return dp[idx][target]
# # Take
# take = False
# if target >= nums[idx]:
# take = f(idx-1, nums, target-nums[idx], dp)
# # Not take
# not_take = f(idx-1, nums, target, dp)
# dp[idx][target] = take or not_take
# return dp[idx][target]
# dp = [[-1 for _ in range(half+1)] for _ in range(len(nums))]
# return f(len(nums)-1, nums, half, dp)
# S3 - Bottom-up Tabulation, TC = N*SUM(nums), SC = N*(SUM(nums))
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
half = total // 2
if len(nums) == 1:
return False
# Build base cases
dp = [[False for _ in range(half+1)] for _ in range(len(nums))]
# For any idx, if target is 0 then the value of dp is True
for i in range(len(dp)):
dp[i][0] = True
# If idx is 0, only when the secondary idx is nums[idx], the dp
# value is true
if nums[0] <= half:
dp[0][nums[0]] = True
# Now form the nested loops
for idx in range(1, len(dp)):
for target in range(1, half+1):
# Take
take = False
if target >= nums[idx]:
diff = target-nums[idx]
# print(f"target: {target}, idx: {idx}, diff")
take = dp[idx-1][target-nums[idx]]
# Not take
not_take = dp[idx-1][target]
dp[idx][target] = take or not_take
return dp[-1][-1]
To me, using HashMap with custom class to record visited node seems much easier to understand.
This is what I mean:
private static class PartitionCoordinate{
int x;
int y;
public PartitionCoordinate(int xValue, int yValue) {
this.x = xValue;
this.y = yValue;
}
@Override
public int hashCode() {
return x + y;
}
@Override
public boolean equals(Object obj) {
if (obj == null) return false;
PartitionCoordinate coordinate = (PartitionCoordinate)obj;
return (coordinate.x == x && coordinate.y == y);
}
}
public static boolean canPartition(List<Integer> nums) {
int total = 0;
int target = 0;
for(int num: nums) {
total += num;
}
if (total%2 == 1) return false;
target = total/2;
Map<PartitionCoordinate, Boolean>set = new HashMap<>();
return partitionDfs(0, target, set, nums, 0);
}
private static boolean partitionDfs(int sum, int target, Map<PartitionCoordinate, Boolean>set,
List<Integer> nums, int index) {
PartitionCoordinate coordinate = new PartitionCoordinate(index, sum);
if(set.containsKey(coordinate)) return set.get(coordinate);
if (sum == target) return true;
if (sum > target || index == nums.size()) return false;
boolean result1 = false;
boolean result2 = false;
int next = sum + nums.get(index);
result1 = partitionDfs(next, target, set, nums, index + 1);
next = sum;
result2 = partitionDfs(next, target, set, nums, index + 1);
set.put(coordinate, (result1 || result2));
return (result1 || result2);
}
Much cleaner version of the bottom up approach
using namespace std;
bool can_partition(std::vector<int> nums) {
int total = accumulate(nums.begin(), nums.end(), 0);
if (total % 2 != 0) return false;
int size = nums.size();
int target = total / 2;
vector<vector<bool>> dp(2, vector<bool>(target + 1, false));
dp[0][0] = dp[1][0] = true;
for (int i = 0; i < size; i++) {
for (int s = 1; s <= target; s++) {
if (!dp[1][s] && s - nums[i] >= 0) {
dp[1][s] = dp[0][s - nums[i]];
}
}
dp[0] = dp[1];
}
return dp[1][target];
}
I think the time complexity is wrong, it should be 2^n -1, so it is O(log2^n) since there will be 2^n -1 nodes.
2^n = 2*2^n-1, 2 is constant
The O(n * target) complexity is not great if “target” was large. It’s possible to solve this in O(n*n) time and O(n) space:
def can_partition(nums: List[int]) → bool:
total = sum(nums)
if total % 2 == 1:
return False
achievable_weights = set([0])
for new_weight in nums:
new_set = achievable_weights.copy()
for previous_sum in achievable_weights:
new_set.add(previous_sum + new_weight)
achievable_weights = new_set
return total // 2 in achievable_weights
If one of the elements in the input array is 2,000,000,000 (still a valid int in Java), I get an OutOfMemoryError with the proposed top-down solution. An alternative to avoid this problem is, instead of having the 2D array memo, to create a class Node that contains two int fields, sum and n, and make the memo be a HashSet of Node instances. Although it takes more millis to run, it doesn’t run out of memory for big elements.