69ms JAVA SuperFast solution with Explanation


  • 0
    F

    First I tried the top-down recursive approach no memoization... solution was easy but I couldn't pass the TLE.

    public class Solution {
        public boolean canPartition(int[] nums) {
            int sum = 0;
            int len = nums.length;
            if (len < 2) {
                return false;
            }
            Arrays.sort(nums);
            for (int i = 0; i < len; i++) {
                sum += nums[i];
            }
            if (sum % 2 != 0) {
                return false;
            }
            return canPartitionHelper(nums, sum / 2);
        }
    
        private boolean canPartitionHelper(int[] nums, int target) {
            return helper2(nums, 0, 0, target);
        }
    
        private boolean helper2(int[] nums, int curr, int currPos, int target) {
            if (curr == target) {
                return true;
            }
            if (currPos == nums.length) {
                return false;
            }
    
            return helper2(nums, curr + nums[currPos], currPos + 1, target) ||
                    helper2(nums, curr, currPos + 1, target);
    
        }
    }
    

    So I wrote the dp (bottom-up) version which is similar to knapsack 01 solution but breaking the execution if there is a solution found.

         private boolean canPartitionHelper(int[] nums, int target) {
            int len = nums.length;
            int[][] dp = new int[len + 1][target + 1];
            for (int i = 1; i <= len; i++) {
                for (int j = 1; j <= target; j++) {
                    if (nums[i - 1] == target) {
                        return true; // the solution is this number by itself and the rest
                    } else if (nums[i - 1] > target) {
                        return false; // there is no way we can get the solution
                    }
    
                    if (dp[i - 1][j] == target) {
                        return true; // the solution was found let's return
                    }
                    if (j - nums[i - 1] >= 0) { // normal dp similar to Knapsack 01
                        dp[i][j] = dp[i - 1][j - nums[i - 1]] + nums[i - 1];
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            return dp[len][target] == target;
        }
    

Log in to reply
 

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