Java backtracking solution - easy to understand


  • 0
    S
    class Solution {
        public boolean canPartitionKSubsets(int[] nums, int k) {
            Map<Integer, Integer> hits = new HashMap<>();
            
            int sum = 0;
            for (int i : nums) {
                sum += i;
            }
            
            if (sum % k != 0) {
                return false;
            }
            
            int target = sum / k;
            
            return helper(nums, k, target, 0, 0);
        }
        
        private boolean helper(int[] nums, int k, int target, int index, int sum) {
            // No more substrings to find :)
            if (k == 0) {
                return true;
            }
            
            // We have reached our target, try to find the target again...
            if (sum == target) {
                return helper(nums, k - 1, target, 0, 0);
            }
            
            // sum is greater than target... this can't be a solution
            if (sum > target) {
                return false;
            }
            
            // Iterate over the following numbers, trying to sum up to the target
            for (int i = index; i < nums.length; i++) {
                
                // Store before we delete
                int curr = nums[i];
                
                // Delete value as used
                nums[i] = 0;
                if (helper(nums, k, target, i + 1, sum + curr)) {
                    return true;
                }
                // Reset value since attempt failed
                nums[i] = curr;
            }
            
            return false;
        }
    }
    

Log in to reply
 

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