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.
1#include <vector>
2#include <numeric>
3using namespace std;
4
5bool canPartition(vector<int>& nums) {
6 int total_sum = accumulate(nums.begin(), nums.end(), 0);
7 if (total_sum % 2 != 0)
8 return false;
9 int target = total_sum / 2;
10 vector<bool> dp(target + 1, false);
11 dp[0] = true;
12 for (int num : nums) {
13 for (int i = target; i >= num; i--) {
14 dp[i] = dp[i] || dp[i - num];
15 }
16 }
17 return dp[target];
18}The implementation follows the same logic as the Python solution. It calculates the total sum and checks if it's odd, returning false if it is. Otherwise, it sets up a DP vector and iterates over the list of numbers to populate the vector, indicating whether subsets achieving certain sums are possible. Specifically, it updates from the back of the DP vector to avoid overwriting values that are yet to be updated in the current number's iteration. Finally, it returns whether the target 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.