Matchsticks to square

XXX. Partition to Equal Sum Subsets

Backtracking

Dynamic Programming

Problem Statement:

Given an array nums, determine if it can be partitioned into four subsets of equal sum. Each number in the array must be part of exactly one subset.

Algorithm:

This problem is solved using backtracking with pruning:

1. Calculate the total sum of the array. If the sum is not divisible by 4, return false immediately.
2. Use an array of size 4 to track the sum of each subset during backtracking.
3. Sort the numbers in descending order to optimize pruning (larger numbers are placed first).
4. For each number, attempt to add it to one of the subsets. If the addition does not exceed the target sum for a subset, continue recursively.
5. If all numbers are placed and the subsets' sums match the target, return true.

Complexity:

Time Complexity: O(4ⁿ), where n is the size of the array. Backtracking explores all possible combinations.
Space Complexity: O(n), for the recursion stack.

Java Implementation:

public class Solution {
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) return false;
        
        // Calculate the total sum of the array
        int sum = 0;
        for (int num : nums) sum += num;
        
        // If the total sum is not divisible by 4, return false
        if (sum % 4 != 0) return false;
        
        // Target sum for each subset
        int target = sum / 4;
        
        // Use backtracking to check if the array can be partitioned
        return dfs(nums, new int[4], 0, target);
    }

    private boolean dfs(int[] nums, int[] sums, int index, int target) {
        // If all numbers are placed, check if all subsets have the target sum
        if (index == nums.length) {
            return sums[0] == target && sums[1] == target && sums[2] == target;
        }

        // Try placing the current number in one of the subsets
        for (int i = 0; i < 4; i++) {
            // Skip if adding the number exceeds the target
            if (sums[i] + nums[index] > target) continue;
            
            // Place the number in the subset
            sums[i] += nums[index];
            
            // Recursively try to place the next number
            if (dfs(nums, sums, index + 1, target)) return true;
            
            // Backtrack: remove the number from the subset
            sums[i] -= nums[index];
        }

        return false;
    }
}