Partition to k equal subset sums [backtracking, BitMask]

XXX. Partition to K Equal Sum Subsets

Dynamic Programming

Recursion

Memoization

Problem Statement:

Given an array of integers a and an integer k, determine if it is possible to partition the array into k subsets where the sum of each subset is equal.

Algorithm:

1. Non-Memoized Version:

1. Calculate the total sum of the array. If it is not divisible by k, return false.
2. Sort the array to optimize the recursion process.
3. Use a recursive function to attempt to partition the array:
• Track the current subset sum and progress through the array with a boolean array seen.
• If a subset matches the target sum, start a new subset.

2. Memoized Version Using String:

This version uses a char[] to track which elements are taken and stores the state in a memoization map:

1. Convert the boolean array into a string representation for memoization.
2. Store the result of the current state to avoid redundant computations.
3. Memoize the results for subsets already computed.

3. Memoized Version Using Bitmask:

This version uses a bitmask to track the taken elements:

1. Use an integer to represent the bitmask of taken elements.
2. Check and update the bitmask using bitwise operations.
3. Memoize the results based on the current bitmask state.

Complexity:

Time Complexity: O(2^n * k) for the bitmask version, where n is the length of the array and k is the number of subsets.
Space Complexity: O(2^n), for the memoization map in the bitmask version.

Java Implementation:

import java.util.*;
import java.util.stream.IntStream;

public class Solution {
    // Non-Memoized Version
    public boolean canPartitionKSubsetsNoMemo(int[] a, int k) {
        int sum = IntStream.of(a).sum();
        Arrays.sort(a);
        // Check if the sum is divisible by k and start the recursive process
        return k != 0 && sum % k == 0 && canPartition(0, a, new boolean[a.length], k - 1, 0, sum / k);
    }

    boolean canPartition(int start, int[] a, boolean[] seen, int k, int sum, int target) {
        // Base case: all subsets are formed
        if (k == 0) return true;
        // If the current subset matches the target, start forming the next subset
        if (sum == target) return canPartition(0, a, seen, k - 1, 0, target);
        // If the current sum exceeds the target, return false
        if (sum > target) return false;

        for (int i = start; i < a.length; i++) {
            if (!seen[i]) {
                // Mark the current element as seen and include it in the subset
                seen[i] = true;
                if (canPartition(i + 1, a, seen, k, sum + a[i], target))
                    return true;
                // Backtrack: unmark the element
                seen[i] = false;
            }
        }
        return false;
    }

    // Memoized Version Using String
    public boolean canPartitionKSubsetsMemoCharArray(int[] a, int k) {
        int sum = IntStream.of(a).sum();
        Arrays.sort(a);
        char[] taken = new char[a.length];
        Arrays.fill(taken, '0');
        // Check if the sum is divisible by k and start the recursive process with memoization
        return k != 0 && sum % k == 0 && canPartition(0, a, taken, k, 0, sum / k, new HashMap<>());
    }

    boolean canPartition(int start, int[] a, char[] seen, int k, int sum, int target, HashMap memo) {
        // Base case: only one subset left
        if (k == 1) return true;
        // If the current sum exceeds the target, return false
        if (sum > target) return false;
        // Check if the current state has been computed before
        String taken = new String(seen);
        if (memo.containsKey(taken)) return memo.get(taken);

        if (sum == target) {
            // If the current subset is formed, try forming the next subset
            boolean ans = canPartition(0, a, seen, k - 1, 0, target, memo);
            memo.put(new String(seen), ans);
            return ans;
        }

        for (int i = start; i < a.length; i++) {
            if (seen[i] == '0') {
                // Mark the current element as seen and include it in the subset
                seen[i] = '1';
                if (canPartition(i + 1, a, seen, k, sum + a[i], target, memo))
                    return true;
                // Backtrack: unmark the element
                seen[i] = '0';
            }
        }

        return false;
    }

    // Memoized Version Using Bitmask
    public boolean canPartitionKSubsets(int[] a, int k) {
        int sum = IntStream.of(a).sum();
        Arrays.sort(a);
        // Check if the sum is divisible by k and start the recursive process with bitmask memoization
        return k != 0 && sum % k == 0 && canPartition(0, a, 0, k, 0, sum / k, new HashMap<>());
    }

    boolean canPartition(int start, int[] a, Integer mask, int k, int sum, int target, HashMap memo) {
        // Base case: only one subset left
        if (k == 1) return true;
        // If the current sum exceeds the target, return false
        if (sum > target) return false;
        // Check if the current state has been computed before
        if (memo.containsKey(mask)) return memo.get(mask);

        if (sum == target) {
            // If the current subset is formed, try forming the next subset
            boolean ans = canPartition(0, a, mask, k - 1, 0, target, memo);
            memo.put(mask, ans);
            return ans;
        }

        for (int i = start; i < a.length; i++) {
            if (((mask >> i) & 1) == 0) {
                // Include the current element in the subset by setting the bit
                mask |= (1 << i);
                if (canPartition(i + 1, a, mask, k, sum + a[i], target, memo))
                    return true;
                // Backtrack: remove the element by clearing the bit
                mask ^= (1 << i);
            }
        }

        return false;
    }
}