Sponsored
Sponsored
This problem can be viewed as a variation of the subset sum problem. The idea is to determine if there is a subset of the given array whose sum is exactly half of the total sum. We use dynamic programming to store information about the previous computations, specifically a DP array where dp[i] indicates whether it's possible to achieve sum i using the elements of the array.
Time Complexity: O(N * target), where N is the number of elements in nums and target is half of the total sum.
Space Complexity: O(target), due to the DP array.
1def canPartition(nums):
2 total_sum = sum(nums)
3 if total_sum % 2 != 0:
4 return False
5 target = total_sum // 2
6 dp = [False] * (target + 1)
7 dp[0] = True
8 for num in nums:
9 for i in range(target, num - 1, -1):
10 dp[i] = dp[i] or dp[i - num]
11 return dp[target]The code starts by calculating the total sum of the array. If this sum is odd, it's impossible to split it into two equal subsets, so it returns false. Otherwise, it computes the target sum as half of the total sum and initializes a DP array dp of size target + 1. The DP array keeps track of which sums can be formed with the numbers encountered so far. It iterates through each number, updating the DP array to indicate whether a subset including that number can achieve each possible sum. Finally, it checks if the target sum is achievable.
This approach uses recursion along with memoization to solve the problem. We try to find a subset that totals half of the overall sum. As we attempt different combinations, we keep track of subproblem solutions we have already computed, which optimizes our solution by avoiding redundant computations.
Time Complexity: O(N * target), where N is the number of elements in nums and target is half of the total sum. The memoization ensures each unique call is computed only once.
Space Complexity: O(N * target) due to the recursive stack and memoization map.
1import java.util.HashMap;
2
The solution checks if the total sum is odd. If it is, partitioning cannot be done equally, so the function returns false. Otherwise, it calls a recursive function that tries to partition the array recursively, considering both including and excluding each number. The function is optimized by storing already computed results for specific states (a combination of current index and remaining target) in a map, thus enabling efficient backtracking without redundant calculations.