Java Solution : Backtracking


  • 0
    S
    public boolean canPartitionKSubsets(int[] nums, int k) {
    
            int totalSum = 0;
            for (int i = 0; i < nums.length ; i++) {
                totalSum+=nums[i];
            }
            if(totalSum%k!=0)
                return false;
            int target = totalSum/k;
            boolean[] used = new boolean[nums.length];
            return canPartitionKSubsetsHelper(nums,target,used,k,0,0);
        }
    
        private boolean canPartitionKSubsetsHelper(int[] nums, int target, boolean[] used,int k,int currentSum,int currentIndex) {
    
            if(k==0)
                return true;
            if(target==currentSum){
                return canPartitionKSubsetsHelper(nums, target, used, k-1, 0, 0);
            }
    
            if (currentSum > target) {
                return false;
            }
            for (int i = currentIndex; i < nums.length; i++) {
                if (used[i]) {
                    continue;
                }
                if (currentSum+nums[i]<=target) {
                    used[i]=true;
                    boolean res = canPartitionKSubsetsHelper(nums, target, used, k, currentSum + nums[i], currentIndex + 1);
                    used[i] = false;
                    if (res)
                        return true;
    
                }
            }
            return false;
        }
    

Log in to reply
 

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