diff options
-rw-r--r-- | partition_equal_subset_sum.c | 36 | ||||
-rw-r--r-- | partition_equal_subset_sum.py | 28 |
2 files changed, 64 insertions, 0 deletions
diff --git a/partition_equal_subset_sum.c b/partition_equal_subset_sum.c new file mode 100644 index 0000000..91156f2 --- /dev/null +++ b/partition_equal_subset_sum.c @@ -0,0 +1,36 @@ +// 416. Partition Equal Subset Sum +#include "leetcode.h" + +/* + * given an integer array 'nums', return true if you can partition the array + * into two subsets such that the sum of the elements in both subsets is equal + * 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 canPartition(int *nums, int numsSize) { + int sum = 0; + for (int i = 0; i < numsSize; i++) + sum += nums[i]; + if ((sum % 2)) + return false; + return is_subset_sum(nums, numsSize, sum / 2); +} + +int main() { + int n1[] = {1, 5, 11, 5}, n2[] = {1, 2, 3, 5}; + printf("%d\n", canPartition(n1, ARRAY_SIZE(n1))); // expect: 1 + printf("%d\n", canPartition(n2, ARRAY_SIZE(n2))); // expect: 0 +} diff --git a/partition_equal_subset_sum.py b/partition_equal_subset_sum.py new file mode 100644 index 0000000..7f563b7 --- /dev/null +++ b/partition_equal_subset_sum.py @@ -0,0 +1,28 @@ +# 416. Partition Equal Subset Sum + +""" +given an integer array 'nums', return true if you can partition the array +into two subsets such that the sum of the elements in both subsets is equal +or false otherwise +""" + + +class Solution(object): + def canPartition(self, nums): + """ + :type nums: List[int] + :rtype: bool + """ + total_sum = sum(nums) + if total_sum & 1: + return False + half_sum, dp = total_sum // 2, 1 + for n in nums: + dp |= dp << n + return dp & 1 << half_sum + + +if __name__ == "__main__": + obj = Solution() + print(obj.canPartition(nums=[1, 5, 11, 5])) + print(obj.canPartition(nums=[1, 2, 3, 5])) |