Partition to K Equal Sum Subsets

Problem Description

Given an integer array nums and an integer k, determine if it is possible to divide this array into k non-empty subsets such that the sum of each subset is equal.

Naive Approach

A brute-force approach would involve generating all possible subsets of the input array and checking if we can form k subsets with equal sums. This approach involves generating all possible combinations of elements, leading to exponential time complexity.

1. Generate all possible subsets of nums.
2. Check if it is possible to select k subsets such that each subset is non-empty and has the same sum.

This approach is highly inefficient and not practical for larger input sizes.

Time Complexity: O(2ⁿ * n), where n is the number of elements in the array.

Space Complexity: O(n), for storing the subsets.

Optimal Approach: Backtracking with Pruning

We can use a backtracking approach with pruning to solve this problem more efficiently.

1. Calculate the target sum: Calculate the sum of all elements in nums. If the sum is not divisible by k, return false immediately because it is impossible to form k equal sum subsets.

2. Calculate the target subset sum: Divide the total sum by k to find the target sum for each subset.

3. Backtracking:

   • Maintain an array subsets of size k to store the current sum of each subset.
   • Recursively try to add each element of nums to one of the subsets.
   • If adding the element to a subset exceeds the target sum, backtrack.
   • If all elements have been added and all subsets have the target sum, return true.
   • If we have explored all possibilities and cannot find a valid partition, return false.

Edge Cases:

• If k is 1, the answer is always true.
• If the sum of nums is not divisible by k, the answer is false.
• If the maximum value in nums is greater than the target subset sum, the answer is false.

Code Example (Java)

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;
        boolean[] used = new boolean[nums.length];
        return canPartition(nums, k, 0, 0, target, used);
    }

    private boolean canPartition(int[] nums, int k, int subsetSum, int start, int target, boolean[] used) {
        if (k == 0) {
            return true;
        }

        if (subsetSum == target) {
            return canPartition(nums, k - 1, 0, 0, target, used);
        }

        for (int i = start; i < nums.length; i++) {
            if (!used[i] && subsetSum + nums[i] <= target) {
                used[i] = true;
                if (canPartition(nums, k, subsetSum + nums[i], i + 1, target, used)) {
                    return true;
                }
                used[i] = false; // Backtrack
            }
        }

        return false;
    }
}

Time and Space Complexity

Time Complexity: O(k * 2ⁿ). Although it looks exponential, the pruning significantly reduces the actual execution time. In the worst-case scenario, we explore a large portion of possible subsets.

Space Complexity: O(n), where n is the length of nums. Dominated by the used array and recursion depth.