Untitled

import java.util.Arrays;

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % k != 0) {
            return false;
        }
        int target = sum / k;

        // Sort in descending order for optimization.
        Arrays.sort(nums);
        reverse(nums);

        // Quick check: if the largest number is greater than target, partitioning is impossible.
        if (nums[0] > target) {
            return false;
        }

        int[] buckets = new int[k];
        return search(nums, 0, buckets, target);
    }

    private boolean search(int[] nums, int index, int[] buckets, int target) {
        if (index == nums.length) {
            // When all numbers have been assigned, check that every bucket sums to target.
            for (int bucket : buckets) {
                if (bucket != target) {
                    return false;
                }
            }
            return true;
        }

        // Try to assign nums[index] to each bucket.
        for (int i = 0; i < buckets.length; i++) {
            // If placing nums[index] in bucket[i] exceeds target, skip.
            if (buckets[i] + nums[index] > target) {
                continue;
            }
            // Avoid duplicate work: if a bucket is empty, then placing the current number in any other empty bucket is equivalent.
            if (i > 0 && buckets[i] == buckets[i - 1]) {
                continue;
            }
            
            buckets[i] += nums[index];
            if (search(nums, index + 1, buckets, target)) {
                return true;
            }
            buckets[i] -= nums[index]; // backtrack

            // If this bucket is still empty after backtracking, no need to try further empty buckets.
            if (buckets[i] == 0) {
                break;
            }
        }
        return false;
    }

    private void reverse(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}