Java brute force O(k*2^(nums.length))


  • 0
    F
    
        public boolean canPartitionKSubsets(int[] nums, int k) {
            int sum=0,max=0;
            for (int n:nums){
                sum+=n;
                max=Math.max(max, n);
            }
            if (k==1)return true;
            int target=sum/k;
            if (sum%k!=0||max>target)return false;
            Arrays.sort(nums);
    //        log.info("nums: {}, sum: {}, sum/k: {}", nums, sum, sum/k);
    
            int mask=(1<<nums.length)-1;
            for (int i=0;i<k;++i){
                boolean found=false;
           // NOTE: loop in descending order to consume big candidates first
                for (int j=mask;j>=1;--j){
                    if ((j&mask)!=j)continue;
    //                log.info("try: {}", j);
                    int sum2=0;
                    for (int l=0;l<20;++l){
                        int mask2=1<<l;
                        if ((mask2&j)!=0)sum2+=nums[l];
                        if (mask2>j)break;
                    }
                    if (sum2==target){
                        mask=mask&(~j);
                        found=true;
                        break;
                    }
                }
              //  log.info("mask: {}, found:{}", mask, found);
                if (!found)return false;
            }
            return true;
    
        }
    

Log in to reply
 

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