Simple solution using sorting and recursion (21 ms)


  • 0
    D
    public static boolean canPartition(int[] nums) {
        if (nums.length == 0) return true;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) return false;
        Arrays.sort(nums);
    
        int targetSum = sum / 2;
        if (nums[nums.length - 1] == targetSum) return true;
        for (int i = 0; i < nums.length; i++) if (sum(nums, i, nums.length - 1, targetSum, 0, new int[200][200])) return true;
        return false;
    }
    
    public static boolean sum(int nums[], int i, int j, int targetSum, int tempSum, int[][] cache) {
        if (targetSum == tempSum)
            return true;
        if (tempSum > targetSum || i == nums.length || j == 0)
            return false;
        if (cache[i][j] != 0) {
            return cache[i][j] == 1;
        }
        boolean res = sum(nums, i + 1, j, targetSum, tempSum + nums[i], cache) || sum(nums, i, j - 1, targetSum, tempSum + nums[j], cache);
        cache[i][j] = res ? 1 : -1;
        return res;
    }

Log in to reply
 

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