very short Java DFS solution.


  • 0

    This is the version without using memorization, which has 8ms running time.

    public class Solution {
        boolean helper(int[] nums, int s, int target){
            if ( (target < 0) || (s>=nums.length) ) return false;
            if ( (target ==0) || helper(nums,s, target-nums[s]) || helper(nums,s+1, target) ) return true;
            return false;
        }
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int num: nums) sum+=num;
            if ((sum & 1) > 0) return false;
            return helper(nums, 0, sum >> 1);
        }
    }
    

  • 0

    @yubad2000 said in very short Java DFS solution.:

    public class Solution {
    boolean helper(int[] nums, int s, int target){
    if ( (target < 0) || (s>=nums.length) ) return false;
    if ( (target ==0) || helper(nums,s, target-nums[s]) || helper(nums,s+1, target) ) return true;
    return false;
    }
    public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num: nums) sum+=num;
    if ((sum & 1) > 0) return false;
    return helper(nums, 0, sum >> 1);
    }
    }

    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,100]

    When I test with this case. Your solution gives wrong answer.


Log in to reply
 

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