698 Partition to K Equal Sum Subsets

Given an array of integers nums and a positive integer k, find whether it's 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's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Note:

1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.

 class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum % k > 0) return false;
        int target = sum / k;
        Arrays.sort(nums);
        int startIdx = nums.length - 1;
        if (nums[startIdx] > target) return false;
        while(startIdx >= 0 && nums[startIdx] == target) {
            startIdx--;
            k--;
        }
        int[] groupSum = new int[k];
        return search(groupSum, startIdx, nums, target);
    }
    public boolean search(int[] groupSum, int startIdx, int[] nums, int target) {
        if (startIdx < 0) return true;
        int num = nums[startIdx--];
        for(int i = 0; i < groupSum.length; i++) {
            if (groupSum[i] + num <= target) {
                groupSum[i] += num;
                if (search(groupSum, startIdx, nums, target)) {
                    return true;
                }
                groupSum[i] -= num;
            }
            if (groupSum[i] == 0) {
                break;
            }
        }
        return false;
    }
}