.png)
Partition Array into K Equal Sum Subsets
Problem Statement
You are given an array of positive integers arr and an integer k.
Your task is to determine if the array can be partitioned into k subsets with equal sum.
Example 1
Input: arr = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: true
Explanation: Possible subsets [5] [1,4] [2,3] [2,3]
Example 2
Input: arr = [1,2,3,4], k = 3
Output: false
Why This Problem Is Important
- Classic backtracking / subset sum problem
- Tests bitmasking, recursion, DP
- Common in Google, Amazon interviews
- Foundation for subset partition problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| 1 | Backtracking | O(k·2^n) | O(n) |
| 2 | DP + Bitmasking | O(n·2^n) | O(2^n) |
Approach 1: Backtracking / DFS
Idea
- Calculate total sum → target sum = total_sum / k
- Use DFS to try assigning numbers to subsets
- Use visited array to avoid reusing elements
Time & Space
- Time: O(k·2^n)
- Space: O(n) (visited array + recursion)
Python
def canPartitionKSubsets(nums, k):
total = sum(nums)
if total % k != 0: return False
target = total // k
n = len(nums)
nums.sort(reverse=True)
visited = [False]*n
def backtrack(start, k, curr_sum):
if k == 0: return True
if curr_sum == target:
return backtrack(0, k-1, 0)
for i in range(start, n):
if not visited[i] and curr_sum + nums[i] <= target:
visited[i] = True
if backtrack(i+1, k, curr_sum + nums[i]):
return True
visited[i] = False
return False
return backtrack(0, k, 0)
# Example
print(canPartitionKSubsets([4,3,2,3,5,2,1], 4)) # True
C++
#include
using namespace std;
bool backtrack(vector& nums, vector& visited, int start, int k, int curr_sum, int target){
if(k==0) return true;
if(curr_sum==target) return backtrack(nums, visited, 0, k-1, 0, target);
for(int i=start;i& nums, int k){
int total = accumulate(nums.begin(), nums.end(), 0);
if(total % k != 0) return false;
int target = total/k;
sort(nums.rbegin(), nums.rend());
vector visited(nums.size(), false);
return backtrack(nums, visited, 0, k, 0, target);
}
int main(){
vector nums = {4,3,2,3,5,2,1};
cout << canPartitionKSubsets(nums, 4); // 1 (true)
}
Java
import java.util.*;
class Main {
public static boolean canPartitionKSubsets(int[] nums, int k){
int total = Arrays.stream(nums).sum();
if(total % k != 0) return false;
int target = total / k;
boolean[] visited = new boolean[nums.length];
Arrays.sort(nums);
int n = nums.length;
return backtrack(nums, visited, n-1, k, 0, target);
}
private static boolean backtrack(int[] nums, boolean[] visited, int start, int k, int currSum, int target){
if(k==0) return true;
if(currSum==target) return backtrack(nums, visited, nums.length-1, k-1, 0, target);
for(int i=start;i>=0;i--){
if(!visited[i] && currSum+nums[i]<=target){
visited[i]=true;
if(backtrack(nums, visited, i-1, k, currSum+nums[i], target)) return true;
visited[i]=false;
}
}
return false;
}
public static void main(String[] args){
int[] nums = {4,3,2,3,5,2,1};
System.out.println(canPartitionKSubsets(nums, 4)); // true
}
}
JavaScript
function canPartitionKSubsets(nums, k){
let total = nums.reduce((a,b)=>a+b,0);
if(total % k !=0) return false;
let target = total / k;
nums.sort((a,b)=>b-a);
let visited = Array(nums.length).fill(false);
function backtrack(start, k, currSum){
if(k===0) return true;
if(currSum===target) return backtrack(0, k-1, 0);
for(let i=start;iC#
using System;
using System.Linq;
class Program {
static bool CanPartitionKSubsets(int[] nums, int k){
int total = nums.Sum();
if(total % k != 0) return false;
int target = total / k;
Array.Sort(nums);
Array.Reverse(nums);
bool[] visited = new bool[nums.Length];
bool Backtrack(int start, int kRemaining, int currSum){
if(kRemaining==0) return true;
if(currSum==target) return Backtrack(0, kRemaining-1, 0);
for(int i=start;iOutput
TrueApproach 2: DP + Bitmasking (Optimized)
Idea
- Represent which elements are used with a bitmask (mask)
- Keep track of current bucket sum (curr_sum)
- Use memoization to avoid recomputation
- Subset sum for each bucket must equal target = total_sum / k
Time & Space
- Time: O(n·2^n) → for each mask (2^n), try n elements
- Space: O(2^n) → memoization table
Python
def canPartitionKSubsets(nums, k):
total = sum(nums)
if total % k != 0: return False
target = total // k
n = len(nums)
nums.sort(reverse=True)
memo = {}
def dp(mask, curr_sum):
if mask == (1<C++
#include
using namespace std;
bool canPartitionKSubsets(vector& nums, int k){
int total = accumulate(nums.begin(), nums.end(), 0);
if(total % k != 0) return false;
int target = total / k;
int n = nums.size();
sort(nums.rbegin(), nums.rend());
unordered_map dp;
function dfs = [&](int mask, int curr){
if(mask == (1< nums = {4,3,2,3,5,2,1};
cout << canPartitionKSubsets(nums, 4); // 1 (true)
}
Java
import java.util.*;
class Main {
public static boolean canPartitionKSubsets(int[] nums, int k){
int total = Arrays.stream(nums).sum();
if(total % k != 0) return false;
int target = total / k;
int n = nums.length;
Arrays.sort(nums);
int[] numsDesc = new int[n];
for(int i=0;i memo = new HashMap<>();
return dfs(0,0,numsDesc,k,target,memo);
}
private static boolean dfs(int mask, int curr, int[] nums, int k, int target, Map memo){
if(mask == (1<JavaScript
function canPartitionKSubsets(nums, k){
let total = nums.reduce((a,b)=>a+b,0);
if(total % k != 0) return false;
let target = total/k;
let n = nums.length;
nums.sort((a,b)=>b-a);
let memo = new Map();
function dfs(mask, curr){
if(mask === (1<C#
using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static bool CanPartitionKSubsets(int[] nums, int k){
int total = nums.Sum();
if(total % k != 0) return false;
int target = total / k;
int n = nums.Length;
Array.Sort(nums);
Array.Reverse(nums);
Dictionary memo = new Dictionary();
bool Dfs(int mask, int curr){
if(mask == (1<Output
TrueFinal Summary
| Approach | Technique | Idea | Time | Space | Pros |
|---|---|---|---|---|---|
| 1 | Backtracking / DFS | Try assigning numbers to k subsets recursively | O(k·2^n) | O(n) | Simple to understand, works for small n |
| 2 | DP + Bitmasking | Use bitmask to represent used numbers + memoization | O(n·2^n) | O(2^n) | Optimized for larger n, avoids recomputation |
Key Points:
- Check total_sum % k == 0 first
- Backtracking is easier for small input
- DP + Bitmasking is better for large input
- Works only with positive integers
- Common in Google, Amazon, Microsoft interviews
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
