Partition to K Equal Sum Subsets - Practice Coding Problems

Partition to K Equal Sum Subsets - Problem

Array Dynamic Programming Backtracking Bit Manipulation Memoization Bitmask Medium

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Each element in the array must belong to exactly one subset, and all subsets must have the same sum.

Note: The order of elements within subsets does not matter, only that each subset has equal sum.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,3,2,3,5,2,1], k = 4

› Output: true

💡 Note: Can form 4 subsets with sum 5 each: [5], [4,1], [3,2], [3,2]. Total sum 20 ÷ 4 = 5 per subset.

Example 2 — Impossible Case

$ Input: nums = [1,2,3,4], k = 3

› Output: false

💡 Note: Total sum is 10, which is not divisible by 3. Cannot form 3 equal-sum subsets.

Example 3 — Single Element

$ Input: nums = [2,2,2,2,3,3], k = 2

› Output: true

💡 Note: Can form 2 subsets with sum 7 each: [2,2,3] and [2,2,3]. Each subset sums to 7.

Constraints

1 ≤ k ≤ nums.length ≤ 16
1 ≤ nums[i] ≤ 10⁴
The frequency of each element is in the range [1, 4]

Visualization

Tap to expand

Understanding the Visualization

Input

Array [4,3,2,3,5,2,1] and k=4 subsets needed

Check

Total sum 20 ÷ 4 = 5, so each subset needs sum 5

Partition

Found valid partition: [5], [4,1], [3,2], [3,2]

Key Takeaway

🎯 Key Insight: First check if total sum is divisible by k, then use backtracking with pruning to find valid partitions

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is that if the total sum isn't divisible by k, it's impossible to create k equal subsets. Best approach uses optimized backtracking with sorting and pruning. Time: O(k^n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Bitmask Dynamic Programming	O(n * 2^n)	O(2^n)	Use bitmask to represent used elements and memoize states
Brute Force Backtracking	O(k^n)	O(n)	Try all possible ways to assign elements to k subsets
Optimized Backtracking	O(k^n)	O(n)	Enhanced backtracking with pruning and sorting optimizations

Bitmask Dynamic Programming — Algorithm Steps

Use bitmask to represent used elements
For each state, try adding unused elements
Memoize results to avoid recomputation
Check if we can form exactly target sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Bitmask State

Each bit represents if an element is used

Memoization

Store results for each (mask, currentSum) state

State Transition

Try adding each unused element to current sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_STATES 100000

typedef struct {
    int mask;
    int sum;
    bool result;
} MemoEntry;

MemoEntry memo[MAX_STATES];
int memoSize = 0;
int target;
int* nums;
int numsSize;

bool findMemo(int mask, int sum) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].mask == mask && memo[i].sum == sum) {
            return memo[i].result;
        }
    }
    return false;  // Not found
}

bool hasMemo(int mask, int sum) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].mask == mask && memo[i].sum == sum) {
            return true;
        }
    }
    return false;
}

void addMemo(int mask, int sum, bool result) {
    if (memoSize < MAX_STATES) {
        memo[memoSize].mask = mask;
        memo[memoSize].sum = sum;
        memo[memoSize].result = result;
        memoSize++;
    }
}

bool dp(int mask, int currentSum) {
    if (currentSum == target) {
        return dp(mask, 0);
    }
    
    if (mask == (1 << numsSize) - 1) {
        return currentSum == 0;
    }
    
    if (hasMemo(mask, currentSum)) {
        return findMemo(mask, currentSum);
    }
    
    for (int i = 0; i < numsSize; i++) {
        if (!(mask & (1 << i)) && currentSum + nums[i] <= target) {
            if (dp(mask | (1 << i), currentSum + nums[i])) {
                addMemo(mask, currentSum, true);
                return true;
            }
        }
    }
    
    addMemo(mask, currentSum, false);
    return false;
}

bool solution(int* numsInput, int numsInputSize, int k) {
    int total = 0;
    for (int i = 0; i < numsInputSize; i++) {
        total += numsInput[i];
    }
    if (total % k != 0) return false;
    
    target = total / k;
    nums = numsInput;
    numsSize = numsInputSize;
    memoSize = 0;
    
    return dp(0, 0);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int numsInput[16];
    int numsInputSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        numsInput[numsInputSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    bool result = solution(numsInput, numsInputSize, k);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n * 2^n)

For each of 2^n possible subsets, we iterate through n elements

⚠ Quadratic Growth

Space Complexity

O(2^n)

Memoization table stores results for each possible bitmask state

⚠ Quadratic Space

125.0K Views

Medium-High Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bitmask Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler