Partition to K Equal Sum Subsets

Question (LC.698)

Given an array of positive integers, is it possible to divide it into k non-empty subsets with equal sum?

Example

I: [4, 3, 2, 3, 5, 2, 1], 4
sort [1,2,2,3,3,4,5]
O: True [1,4], [2,3], [2,3], [5]

Approach

This is no longer special case where we know the other subset is guaranteed to exist. Exclusive search with remaining numbers.

Step 1 Define recursion
subsetSumHelper(int[] nums, boolean[] used, int k, int startIndex, int curSum, int target)
will determine whether the remaining list can be partitioned into k groups of the target sum

Step 2 Recursive calls
for (int i = startIndex; i < nums.length; i++)
    if used
        continue
    if nums[i] > target
        return false
    used[i] = true
    subsetSumHelper(nums, used, k, i+1, curSum + nums[i], target)
    used[i] = false

Step 3 Base cases
if (k == 0)
    return true

Code

public boolean canPartitionKSubsets(int[] nums, int k) {
    // edge check
    if (nums == null || nums.length == 0 || k < 1) {
        return false;
    }
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % k != 0) {
        return false;
    }
    // prep search
    boolean used[] = new boolean[nums.length];
    Arrays.sort(nums);
    return subsetSumHelper(nums, used, k, 0, 0, sum / k);
}

private boolean subsetSumHelper(int[] nums, 
                                boolean[] used, 
                                int k, 
                                int startIndex, 
                                int curSum, 
                                int target) {
    // base case
    if (k == 0) {
        return true;
    }
    if (curSum == target) {
        return subsetSumHelper(nums, used, k-1, 0, 0, target);
    }
    // recursive calls
    for (int i = startIndex; i < nums.length; i++) {
        if (used[i]) {
            continue;
        }
        if (curSum + nums[i] > target) {
            return false;
        }
        used[i] = true;
        if (subsetSumHelper(nums, used, k, i+1, curSum + nums[i], target)) return true;
        used[i] = false;  
    }
    return false;
}