algoadvance

Leetcode 698. Partition to K Equal Sum Subsets

Problem Statement

The problem “Partition to K Equal Sum Subsets” is defined as follows:

Given an array of integers nums and an integer k, determine if it is possible to partition this array into k non-empty subsets whose sums are all equal.

Clarifying Questions

  1. Can some elements be zero or negative?
    • No, all elements in the array are positive integers.
  2. Is k guaranteed to be less than or equal to the length of the array?
    • Yes, k is always less than or equal to the length of the array.
  3. Can the array be modified?
    • Yes, in the context of solving the problem, modifying the array is allowed.
  4. Are duplicate elements in the array allowed?
    • Yes, there can be duplicate elements in the array.

Strategy

We need to partition the array into k subsets such that each subset has the same sum. Here’s the strategy:

  1. Initial Checks:
    • Calculate the total sum of the array. If this sum is not divisible by k, then it’s impossible to partition as required.
    • Determine the target sum for each subset as target = total_sum / k.
  2. Backtracking:
    • Use a backtracking approach to try and form subsets with the target sum.
    • Keep track of which elements have been used in forming subsets.
    • Recursively attempt to form each subset, reducing the target sum as elements are added to a subset.
  3. Pruning:
    • Sort the array in descending order. Larger elements first helps in faster invalidation of paths that can’t reach the target sum.
    • If an element is larger than the target sum, return false.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    bool canPartitionKSubsets(std::vector<int>& nums, int k) {
        int totalSum = 0;
        for (int val : nums) {
            totalSum += val;
        }
        
        if (totalSum % k != 0) return false;
        
        int target = totalSum / k;
        std::sort(nums.begin(), nums.end(), std::greater<int>());
        std::vector<bool> used(nums.size(), false);
        
        return backtrack(nums, used, k, 0, 0, target);
    }
    
private:
    bool backtrack(const std::vector<int>& nums, std::vector<bool>& used, int k, int currentSum, int startIndex, int target) {
        if (k == 1) return true;  // Only one subset remaining, it must be valid
        if (currentSum == target) {
            return backtrack(nums, used, k - 1, 0, 0, target);
        }
        
        for (int i = startIndex; i < nums.size(); ++i) {
            if (used[i] || currentSum + nums[i] > target) continue;
            used[i] = true;
            if (backtrack(nums, used, k, currentSum + nums[i], i + 1, target)) {
                return true;
            }
            used[i] = false;
            
            // Optimization: If adding the current element can't satisfy the condition, no need to try other elements
            if (currentSum == 0) return false;
        }
        
        return false;
    }
};

Time Complexity

  1. Sorting Time Complexity:
    • O(n log n) where n is the number of elements in the array.
  2. Backtracking Time Complexity:
    • There are potentially O(2^n) subsets to check in the worst case, but pruning and sorting elements reduce the actual number of checks significantly.
  3. Overall Time Complexity:
    • The backtracking solution is optimized with pruning and sorting, but in the worst case scenario, it is still exponential: O(k * 2^n). However, typical cases will be faster due to early exits on invalid paths.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI