Java BackTracking with comments, 10ms beats 96%


  • 0
    F

    Because you only need to find 1 instance, you can stop the BFS and return true, whereas for DP you have to iterate and fill the entire table.

    class Solution {
        boolean res = false;
        public boolean canPartition(int[] nums) {
            long sum = 0;
            for(int i : nums){
                sum += i;
            }
            /* if not even return false */
            if((sum & 1) != 0){ return false; }
            Arrays.sort(nums);
            helper(nums, sum / 2, 0);
            return res;
        }
        private void helper(int[] nums, long sum, int pos){
            if(sum == 0){
                res = true;
                return;
            }
            if(sum < 0 || pos == nums.length){ return; }
            /* if res is true, means we already found it, do not continue BFS */
            while(pos < nums.length && !res){
                helper(nums, sum - nums[pos], pos + 1);
                /* skip duplicates */
                while(pos + 1 < nums.length && nums[pos] == nums[pos + 1]){ pos++; }
                pos++;
            }
    }
    

Log in to reply
 

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