What is the brute force approach and complexity for Partition to K Equal Sum Subsets?

Put each number into one of the k buckets in turn; check the buckets at the end with time complexity O(k^N) and space complexity O(N + k).

What is the optimal approach and complexity for Partition to K Equal Sum Subsets?

dp[mask] = can this set of numbers be placed, with the open bucket at sum % target? with optimal time complexity O(N · 2^N) and space complexity O(2^N).

How do you identify the pattern for Partition to K Equal Sum Subsets?

Look for key signals in the prompt: "split into k groups with equal sums" indicates Each group must be total / k. One subset is no longer enough: the groups are k disjoint subsets that cover every number.; "each number goes in exactly one group" indicates A number cannot be shared between groups, so each number is used once.; "return true or false" indicates Only feasibility matters, so a bitmask of the numbers already placed is enough..

Partition to K Equal Sum Subsets

Medium·LeetCode #698 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

You get an array of whole numbers, nums, and a number k. Can you split nums into k non-empty groups so that every group has the same sum?

Every number goes into exactly one group. Return true if it is possible, and false if it is not.

Input

An array nums and an integer k.

Output

true if the numbers can be split into k groups with equal sums, otherwise false. The function is bool canPartitionKSubsets(vector<int>& nums, int k).

Example 1

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

Output: true

The groups (5), (1, 4), (2, 3) and (2, 3) each sum to 5.

Example 2

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

Output: false

The total is 10, which does not divide into 3 equal whole sums, so the answer is false at once.

Constraints

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“split into k groups with equal sums”

→ Each group must be total / k. One subset is no longer enough: the groups are k disjoint subsets that cover every number.

“each number goes in exactly one group”

→ A number cannot be shared between groups, so each number is used once.

“return true or false”

→ Only feasibility matters, so a bitmask of the numbers already placed is enough.

Approach Complexity Ladder

Brute Force — try every group for every numberO(k^N)O(N + k)

Put each number into one of the k buckets in turn; check the buckets at the end

Better — backtracking with pruningO(k^N)O(N + k)

Sort big to small; skip any bucket the number does not fit in; try only one empty bucket

Optimal — bitmask DP over the numbers already placedO(N · 2^N)O(2^N)

dp[mask] = can this set of numbers be placed, with the open bucket at sum % target?

Brute Force Intuition

Call the buckets B0 … B(k−1). For the first number, try B0, then B1, and so on. The next number does the same, and so on. Only when every number is placed do we check that every bucket holds total / k. There are k^N ways to place the numbers, so this checks all of them.

Recognition rule for this sub-pattern:

Two equal/close groups ⇔ find a subset with sum near total/2.

Remember this · DP — Knapsack

Trigger

Pick a subset to hit a target sum / capacity, partition into two groups, count the ways to reach an amount.

Think

Is this "choose some items so their total is X"?

Key question

Can each item be used once (loop capacity backwards) or many times (loop forwards)?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Knapsack translate into production architectures and low-level memory mechanics.

LLD Architecture