698. Partition to K Equal Sum Subsets

Problem

Partition to K Equal Sum Subsets - LeetCodeLeetCode

Intuition

Initially this feels like a DP problem seeing we need to explore all the possibilities and somewhere we can optimise the problem. But it is a simple recursion/DFS problems. That is you check all the possibilities to form the subsets. The recursion tree will not end up with any overlapping subproblems.

That is why it is more important to come up with recursive solution for DP problems rather than pre maturely optimising them.

Coming to this problem, we need to do few pre-checks:

• Check if totalSum can be divided into "k" equal subsets

• Explore all the possible paths of building subsets

We pick on element and recursively check if there exists other elements that can form the target sum i.e. totalSum/k. If we find a subset we mark the elements we need as visited using a boolean array.

Time Complexity

$O(k*2^n)$

k -> Number of subsets

n -> Total number of elements in the input array

For all the possible subsets we need to pick or not pick the elements. 2^n

Space Complexity

O(N)

For the visited array.

Solution

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        // N - > nums.length k-> Number of subsets;
        // Time Complexity: O(k* 2^n), k-> for finding k number of subsets and each element 
        // can be included in the subset or not
        // Space Complexity: O(N)
        // This method checks if the array nums can be partitioned into k subsets with equal sums.

        int totalSum = 0;
        for (int num : nums) {
            totalSum += num; // Calculate the total sum of the array.
        }

        if (totalSum % k != 0) {
            return false; // If the total sum is not divisible by k, partitioning is not possible.
        }

        int target = totalSum / k; // Calculate the target sum for each subset.

        boolean[] visited = new boolean[nums.length]; // Array to track visited elements.

        return canBePartitioned(nums, visited, k, 0, 0, target); // Recursively check if partitioning is possible.
    }

    private boolean canBePartitioned(int[] nums, boolean[] visited, int k, int start, int current, int target) {
        // Recursive helper method to check if the array can be partitioned into k subsets.

        if (k == 0) {
            return true; // Base case: If k subsets have been formed, return true.
        }
        if (current > target) {
            return false; // If the current sum exceeds the target, return false.
        }
        if (current == target) {
            return canBePartitioned(nums, visited, k - 1, 0, 0, target); // If the current sum is equal to the target, move on to the next subset.
        }

        for (int i = start; i < nums.length; i++) {
            if (visited[i]) {
                continue; // Skip already visited elements.
            }
            visited[i] = true; // Mark the current element as visited.
            if (canBePartitioned(nums, visited, k, i + 1, current + nums[i], target)) {
                return true; // Recursively check if partitioning is possible with the current element.
            }
            visited[i] = false; // Backtrack: Mark the current element as not visited.
        }
        return false; // If partitioning is not possible with the current element, return false.
    }
}