canPartitionKSubsets

gistfile1.txt

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        int max = 0;
        for(int e: nums) {
            sum += e;
            max = Math.max(max, e);
        }
        
        if(sum % k > 0 || max > (sum / k)) return false;
        int[] dp = new int[k];
        Arrays.fill(dp, sum / k);
        return backTracking(nums, 0, dp);
    }
    
    private boolean backTracking(int[] nums, int i, int[] dp) {
        if(i >= nums.length) return true;
        
        for(int j = 0; j < dp.length; j++) {
            if(dp[j] - nums[i] >= 0) {
                dp[j] -= nums[i];
                if(backTracking(nums, i + 1, dp)) {
                    return true;
                }
                dp[j] += nums[i];
            }
        }
        
        return false;
    }
}