Partition Equal Subset Sum - Leetcode Solution

Problem:

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.

Solution:

To solve this problem, we can use dynamic programming. We can start by calculating the sum of all elements in the input array. If the sum of all elements is odd, we can't divide the array into two subsets with equal sums, so we return false. If the sum of all elements is even, we can divide the array into two subsets with equal sums. We can then use dynamic programming to solve the problem.

We can create a boolean two-dimensional array dp, where dp[i][j] represents whether it is possible to construct a subset of the first i elements of the input array, whose sum is j. If dp[nums.length][sum_of_all_elements / 2] is true, we return true, otherwise we return false.

To fill the dp array, we can follow these steps:

1. Initialize dp[i][0] to true, because we can always create a subset of sum 0 with any set of elements.
2. Initialize dp[0][j] to false, because we can't create a subset using an empty set of elements.
3. For each element nums[i-1], we check if we can create a subset of sum j using either nums[i-1] or not. We can use it only if nums[i-1] is less than or equal to j. Otherwise, we can't consider it.
4. If we can create a subset of sum j without using nums[i-1], we can just copy the value from dp[i-1][j]. Otherwise, we need to check if we can create a subset of sum j-nums[i-1] using the first i-1 elements. If yes, then we can create a subset of sum j using the first i-1 elements and nums[i-1].

Here's the Java code for the solution:

class Solution { public boolean canPartition(int[] nums) { int sum = 0; for (int i : nums) { sum += i; } if (sum % 2 == 1) { return false; } sum /= 2; boolean[][] dp = new boolean[nums.length + 1][sum + 1]; for (int i = 0; i <= nums.length; i++) { dp[i][0] = true; } for (int j = 1; j <= sum; j++) { dp[0][j] = false; } for (int i = 1; i <= nums.length; i++) { for (int j = 1; j <= sum; j++) { if (nums[i - 1] > j) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]; } } } return dp[nums.length][sum]; } }

Time complexity: O(n * sum), where n is the length of the input array and sum is the sum of all elements in the input array. Space complexity: O(n * sum), we use a two-dimensional dp array of size (n+1) * (sum+1).

1