Java Recursive & DP Solution.


  • 0
    S

    Partition Equal Subset Sum

    1. First thing to check is whether the sum of all elements is odd. If yes, then it's impossible to divide it into two sets of equal sum.

    2. Next, now we have an even sum, we want to check whether there exists a subarray which has sum equal to half the sum of the total sum.

    There are two ways to do so -

    1. Recursive
    2. Using Dynamic Programming.

    Recursive:

    The logic is that in order to find a subarray, we either include an element or we do not.
    So we start from the last index and recursively call the same function 'isSumSubarray'.

    public class Solution {
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length < 1) {
                return true;
            }
            int sum = 0;
            for (int i : nums) {
                sum += i;
            }
            if (sum % 2 == 1) {
                return false;
            }
            sum /= 2;
            // find a subarray whose sum of elements equals sum.
            return isSumSubarray(nums, sum, nums.length - 1);
        }
        
        private boolean isSumSubarray(int[] nums, int sum, int last) {
            if (sum == 0) {
                return true;
            }
            // since the array contains only positive elements
            if (sum < 0 || last < 0) {
                return false;
            }
            return (isSumSubarray(nums, sum, last - 1) || 
                isSumSubarray(nums, sum - nums[last], last - 1));
        }
    }
    

    DP Solution:

    The above solution will give TLE because there'll be overlapping sub problems.
    In this solution we will create a 2D boolean array with row size as sum/2 + 1 and col size as size of given array + 1.
    The element dp[i][j] would represent whether we can achieve a sum of i with a subarray ending at index j - 1.

    The first row would be all true and first column (excluding dp[0][0]) will be all false.

    public class Solution {
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length < 1) {
                return true;
            }
            int sum = 0;
            for (int i : nums) {
                sum += i;
            }
            if (sum % 2 == 1) {
                return false;
            }
            sum /= 2;
            // DP Solution -- helpful when sum is not too big.
            boolean[][] dp = new boolean[sum + 1][nums.length + 1];
            // firt row
            for (int j = 0; j < dp[0].length; j++) {
                dp[0][j] = true;
            }
            // first col
            for (int i = 1; i < dp.length; i++) {
                dp[i][0] = false;
            }
            // rest
            for (int i = 1; i <= sum; i++) {
                for (int j = 1; j <= nums.length; j++) {
                    dp[i][j] = dp[i][j - 1];
                    if (i - nums[j - 1] >= 0) {
                        dp[i][j] = dp[i][j] || dp[i - nums[j - 1]][j - 1];
                    }
                }
            }
            return dp[sum][nums.length];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.