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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 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.