Partition to K Equal Sum Subsets

Question

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4,3,2,3,5,2,1], k = 4 Output: true Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

Input: nums = [1,2,3,4], k = 3 Output: false

Constraints:

• 1 <= k <= nums.length <= 16
• 1 <= nums[i] <= 10^4
• The frequency of each element is in the range [1, 4].

Solution:

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        // Calculate the total sum of the array elements
        int sum = Arrays.stream(nums).sum();
        boolean[] used = new boolean[nums.length];
        
        // If total sum is not divisible by k, partitioning into k subsets is impossible
        if (sum % k != 0) {
            return false;
        }
        
        // Sort the array to help with pruning and start with larger numbers
        Arrays.sort(nums);
        
        // Start the DFS search to partition the array into k subsets with sum sum/k
        return dfs(nums, k, 0, 0, used, sum / k);
    }
    
    boolean dfs(int[] nums, int k, int currSum, int idx, boolean[] used, int target) {
        // Base case: if only 1 subset is needed, the rest of the elements must already form a valid subset
        if (k == 1) {
            return true;
        }
        
        // If the current subset sum matches the target, move on to form the next subset
        if (currSum == target) {
            return dfs(nums, k - 1, 0, 0, used, target);
        }
        
        // Try to form the current subset by adding elements from nums
        for (int i = idx; i < nums.length; i++) {
            // Skip if the element is already used or if it leads to redundant checks (skip duplicates)
            if (used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            
            // Mark the current element as used
            used[i] = true;
            
            // Recursively try to form the subset by including nums[i]
            if (dfs(nums, k, currSum + nums[i], i + 1, used, target)) {
                return true;
            }
            
            // Backtrack if the current element doesn't lead to a solution
            used[i] = false;
        }
        
        // If no valid partitioning is found, return false
        return false;
    }
}