aboutsummaryrefslogtreecommitdiff
path: root/partition_equal_subset_sum.c
diff options
context:
space:
mode:
Diffstat (limited to 'partition_equal_subset_sum.c')
-rw-r--r--partition_equal_subset_sum.c37
1 files changed, 24 insertions, 13 deletions
diff --git a/partition_equal_subset_sum.c b/partition_equal_subset_sum.c
index 91156f2..d71deb5 100644
--- a/partition_equal_subset_sum.c
+++ b/partition_equal_subset_sum.c
@@ -7,26 +7,37 @@
* or false otherwise
*/
-bool is_subset_sum(int *nums, int numsSize, int sum) {
- bool dp[numsSize + 1][numsSize + 1];
- for (int i = 0; i <= numsSize; i++)
- dp[i][0] = true;
- for (int i = 1; i <= sum; i++)
- dp[0][i] = false;
- for (int i = 1; i <= numsSize; i++)
- for (int j = 1; j <= sum; j++)
- dp[i][j] = nums[i - 1] <= j ? dp[i - 1][j - nums[i - 1]] || dp[i - 1][j]
- : dp[i - 1][j];
- return dp[numsSize][sum];
+bool memo(int *nums, int **dp, int sum, int idx, int n) {
+ if (!sum)
+ return true;
+ if (idx >= n)
+ return false;
+ if (dp[idx][sum] != -1)
+ return dp[idx][sum];
+ bool pick = false, no_pick = false;
+ if (nums[idx] <= sum)
+ pick = memo(nums, dp, sum - nums[idx], idx + 1, n);
+ no_pick = memo(nums, dp, sum, idx + 1, n);
+ return dp[idx][sum] = (pick || no_pick);
}
bool canPartition(int *nums, int numsSize) {
int sum = 0;
for (int i = 0; i < numsSize; i++)
sum += nums[i];
- if ((sum % 2))
+ if (sum & 1)
return false;
- return is_subset_sum(nums, numsSize, sum / 2);
+ int **dp = (int **)malloc(numsSize * sizeof(int *));
+ for (int i = 0; i < numsSize; i++) {
+ dp[i] = (int *)malloc(((sum >> 1) + 1) * sizeof(int));
+ for (int j = 0; j < ((sum >> 1) + 1); ++j)
+ dp[i][j] = -1;
+ }
+ bool ans = memo(nums, dp, sum >> 1, 0, numsSize);
+ for (int i = 0; i < numsSize; i++)
+ free(dp[i]);
+ free(dp);
+ return ans;
}
int main() {