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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
public bool CanPartition(int[] nums) {
int total_sum = 0;
foreach (int num in nums) total_sum += num;
if (total_sum % 2 != 0) return false;
return CanPartition(nums, 0, total_sum / 2, new Dictionary<string, bool>());
}
private bool CanPartition(int[] nums, int index, int target, Dictionary<string, bool> memo) {
if (target == 0) return true;
if (index >= nums.Length) return false;
string memoKey = index + "," + target;
if (memo.ContainsKey(memoKey)) return memo[memoKey];
bool result = CanPartition(nums, index + 1, target, memo) || (target >= nums[index] && CanPartition(nums, index + 1, target - nums[index], memo));
memo[memoKey] = result;
return result;
}
}Similarly, this C# solution follows the logic of handling odd total sums by returning false immediately. A recursive function runs to attempt partitioning, with memoization used to store whether specific index and target combinations have already been resolved, enhancing efficiency.