Java 15ms recursive solution


  • 0
    G
    public class Solution {
        public boolean canPartition(int[] nums) {
            int sum=0;
            int max=0;
            int min=101;
            for(int el: nums){
                sum+=el;
                max=Math.max(max, el);
                min=Math.min(min, el);
            }
            if((sum & 1) == 1)
                return false;
            if(max==sum/2)
                return true;
            if(max+min>sum/2)
                return false;
            return find(nums, 0, sum/2);
        }
        
        private boolean find(int[] nums, int idx, int sum){
            for(int i=idx; i<nums.length; i++)
                if(nums[i]==sum)
                    return true;
            
            if(idx==nums.length-1)
                return false;
                
            Set<Integer> tried = new HashSet<>();   
            for(int i=idx; i<nums.length; i++)
                if(nums[i]<sum && !tried.contains(nums[i])){
                    int tmp=nums[i];
                    nums[i]=nums[idx];
                    if(find(nums, idx+1, sum-tmp))
                        return true;
                    nums[i]=tmp;
                    tried.add(tmp);
                }
                
            return false;
        }
    }
    

Log in to reply
 

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