300. Partition of a Set Into K Subsets With Equal Sum

Given an array of n positive integers and an integer k, print 'Yes' if the array can be partitioned into k non-empty subsets such that every subset has the same sum (every element must be used in exactly one subset), otherwise print 'No'.

Input: The first line contains an integer n. The second line contains n space-separated positive integers. The third line contains the integer k. Output: Print 'Yes' if the array can be split into k equal-sum subsets, otherwise print 'No'.

1 <= k <= n <= 16, 1 <= arr[i] <= 1000

This is a genuine generalization of the classic 'Partition Problem' (which is just the special case k=2) - recognizing this connection situates the problem within a broader, recognizable family rather than treating it as an entirely novel challenge.

Check whether an array can be split into k subsets that all have the exact same sum. Brute force: Try every possible way to partition the array into k labeled groups directly (an enormous combinatorial search over all possible groupings) - this is what the backtracking approach constrains significantly, by filling subsets ONE AT A TIME to a fixed target rather than considering all groupings simultaneously. Optimised: Filling subsets ONE AT A TIME (completing one to the target sum before even considering the next) rather than trying to assign every element to one of k groups simultaneously dramatically reduces the branching factor - combined with the quick upfront feasibility checks (divisibility, largest element), many impossible cases are rejected instantly before any real search begins.

First check that the total sum is divisible by k (otherwise immediately print 'No') and compute the target = total/k. Then recursively try assigning each of the n elements to one of the k subsets in turn, exploring all k^n possible assignments, and check at the end whether every subset's sum equals the target. This directly enumerates the entire assignment space. Time: O(k^n) Space: O(n) recursion depth

Since n <= 16, check total sum divisible by k and compute target = total/k, then represent which elements have been used so far as a bitmask. Define dp[mask] as the remaining capacity of the subset currently being filled when exactly the elements in mask have been placed into completed or in-progress subsets (dp[0] = target). For each mask, for every unused element i whose value doesn't exceed dp[mask], transition to dp[mask | (1<<i)]: if the element exactly fills the current subset's remaining capacity, the new remaining capacity resets to target (starting a new subset), otherwise it decreases by the element's value. The array can be partitioned iff dp[(1<<n)-1] is reachable and ends at 0. This turns the combinatorial search into a bounded table of 2^n states. Time: O(2^n * n) Space: O(2^n)

Check total sum divisible by k and compute target = total/k, then sort the array descending (placing larger elements first prunes faster). Maintain an array of k running subset sums, and recursively try placing each element into one of the k subsets whose running sum plus the element wouldn't exceed the target, backtracking immediately on any subset that would overflow, and skipping over subsets that currently have the same running sum as one already tried at this position (to avoid redundant symmetric branches). This greatly prunes the search compared to trying every raw k^n assignment, though the worst case is still exponential. Time: Exponential worst case, much reduced in practice Space: O(n + k)

1. First compute the target sum per subset as (total sum) / k - if this isn't a whole number, or if any single element exceeds it, the answer is immediately No. 2. Fill ONE subset at a time, up to the target sum, before moving on to filling the next subset. 3. Skip elements already used in an earlier subset, and skip any element that would push the CURRENT subset's running sum past the target - backtrack when a subset can't be completed with the remaining unused elements.

Time: Exponential in the worst case (k^n roughly, in the naive framing), though the one-subset-at-a-time filling strategy and upfront pruning make it tractable for the given constraint (n<=16). Space: O(n) for tracking which elements are used, plus O(k) for the recursion depth across subsets.

Test k = n (each element its own subset), a total sum not evenly divisible by k (immediately 'No'), and n = 16 for performance.

Be ready to state the two quick upfront feasibility checks explicitly (total sum divisible by k, and no single element exceeding the target) - these cheap checks can immediately reject many impossible inputs before any expensive search begins.