Intuitive java solution


  • 0
    R

    My solution is based on simple backtracking. For DP I am storing the start index and the left sum. This because left and right sum will vary with length. So you can also keep right sum in the dp. Here is the code

    public class Solution {
        int[][] map;
        public boolean canPartition(int[] nums) {
            if(nums.length == 0) {
                return true;
            }
            int sum = 0;
            for(int x : nums) {
                sum += x;
            }
            map = new int[nums.length][sum+1];
            return canPartAux(nums,0,0,0);
        }
        
        public boolean canPartAux(int[] nums, int start, int left, int right) {
            if(start == nums.length) {
                return left == right;
            }
            
            if(map[start][left] != 0) {
                return map[start][left] == 1;
            }
            
            boolean result =  canPartAux(nums,start+1, left+nums[start], right) || canPartAux(nums,start+1,left,right+nums[start]);
            map[start][left] = result ? 1 : -1;
            return result;
        }
    }
    

Log in to reply
 

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