LeetCode 698: Partition to K Equal Sum Subsets Solution

Master LeetCode problem 698 (Partition to K Equal Sum Subsets), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

698. Partition to K Equal Sum Subsets

Medium

Array Dynamic Programming Backtracking Bit Manipulation Memoization Bitmask

Problem Explanation

Explanation

To solve this problem, we can use backtracking to try all possible ways of partitioning the array into k subsets. At each step, we try to add the current element from the array to one of the k subsets. If we can successfully partition the array into k subsets such that each subset has the same sum, we return true; otherwise, we return false.

Here is an outline of the algorithm:

Calculate the target sum by dividing the total sum of the array by k.
Sort the array in descending order to try larger elements first.
Use a recursive backtracking function to try adding each element to one of the k subsets.
Keep track of the current sum of each subset and the index of the element being considered.
If we successfully partition the array into k subsets, return true; otherwise, return false.

Time complexity: O(k * 2^n), where n is the number of elements in the array and k is the number of subsets. Space complexity: O(n)

Solution Code

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;
        Arrays.sort(nums);
        int n = nums.length;
        int[] subsetSums = new int[k];
        return backtrack(nums, n - 1, subsetSums, target, k);
    }
    
    private boolean backtrack(int[] nums, int index, int[] subsetSums, int target, int k) {
        if (index == -1) {
            for (int sum : subsetSums) {
                if (sum != target) {
                    return false;
                }
            }
            return true;
        }
        for (int i = 0; i < k; i++) {
            if (subsetSums[i] + nums[index] <= target) {
                subsetSums[i] += nums[index];
                if (backtrack(nums, index - 1, subsetSums, target, k)) {
                    return true;
                }
                subsetSums[i] -= nums[index];
            }
            if (subsetSums[i] == 0) {
                break;
            }
        }
        return false;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 698 (Partition to K Equal Sum Subsets)?

This page provides optimized solutions for LeetCode problem 698 (Partition to K Equal Sum Subsets) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 698 (Partition to K Equal Sum Subsets)?

The time complexity for LeetCode 698 (Partition to K Equal Sum Subsets) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 698 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 698 in Java, C++, or Python.

Back to LeetCode Solutions