Related: LeetCode 416 - Partition Equal Subset Sum
Partition of a set into K subsets with equal sum
Partition of a set into K subsets with equal sum + 3|K Partition Problem
LeetCode 698 - Partition to K Equal Sum Subsets
http://www.techiedelight.com/3-partition-problem/
http://www.geeksforgeeks.org/partition-set-k-subsets-equal-sum
Given an integer array of N elements, the task is to divide this array into K non-empty subsets such that the sum of elements in every subset is same. All elements of this array should be part of exactly one partition.
http://www.techiedelight.com/k-partition-problem-print-all-subsets/
Partition of a set into K subsets with equal sum
Partition of a set into K subsets with equal sum + 3|K Partition Problem
LeetCode 698 - Partition to K Equal Sum Subsets
http://www.techiedelight.com/3-partition-problem/
3-partition problem: Given a set S of positive integers, determine if it can be partitioned into three disjoint subsets that all have same sum and they cover S.
For example,
S = { 7, 3, 2, 1, 5, 4, 8 }
We can partition S into three partitions each having sum 10.
S1 = {7, 3}
S2 = {5, 4, 1}
S3 = {8, 2}
S2 = {5, 4, 1}
S3 = {8, 2}
Note that there can be multiple solutions to a single set.
If St is divisible by 3, we check if 3 subsets with sum of elements equal to St/3 exists or not. We can find this by considering each item in the given array one by one and for each item there are three possibilities –
- We include the current item in the first subset and recurse for remaining items with remaining sum.
- We include the current item in the second subset and recurse for remaining items with remaining sum.
- We include the current item in the third subset and recurse for remaining items with remaining sum.
The base case of the recursion would be when no items are left. We return true when 3 subsets each with zero sum are found. We can optimize our code by calling case 2 only if case 1 doesn’t result in solution, and case 3 only if case 1 and 2 doesn’t result in any solution.
public static boolean subsetSum(int[] S, int n, int a, int b, int c)
{
// return true if subset is found
if (a == 0 && b == 0 && c == 0) {
return true;
}
// base case: no items left
if (n < 0) {
return false;
}
// Case 1. current item becomes part of first subset
boolean A = false;
if (a - S[n] >= 0) {
A = subsetSum(S, n - 1, a - S[n], b, c);
}
// Case 2. current item becomes part of second subset
boolean B = false;
if (!A && (b - S[n] >= 0)) {
B = subsetSum(S, n - 1, a, b - S[n], c);
}
// Case 3. current item becomes part of third subset
boolean C = false;
if ((!A && !B) && (c - S[n] >= 0)) {
C = subsetSum(S, n - 1, a, b, c - S[n]);
}
// return true if we get solution
return A || B || C;
}
// Function for solving 3-partition problem. It return true if given
// set S[0..n-1] can be divided into three subsets with equal sum
public static boolean partition(int[] S)
{
if (S.length < 3) {
return false;
}
// get sum of all elements in the set
int sum = Arrays.stream(S).sum();
// return true if sum is divisble by 3 and the set can can
// be divided into three subsets with equal sum
return (sum % 3) == 0 &&
subsetSum(S, S.length - 1, sum/3, sum/3, sum/3);
}
X. DFS+Cache
public static boolean subsetSum(int[] S, int n, int a, int b, int c,
Map<String, Boolean> lookup)
{
// return true if subset is found
if (a == 0 && b == 0 && c == 0) {
return true;
}
// base case: no items left
if (n < 0) {
return false;
}
// construct a unique map key from dynamic elements of the input
String key = a + "|" + b + "|" + c + "|" + n;
// if sub-problem is seen for the first time, solve it and
// store its result in a map
if (!lookup.containsKey(key))
{
// Case 1. current item becomes part of first subset
boolean A = false;
if (a - S[n] >= 0) {
A = subsetSum(S, n - 1, a - S[n], b, c, lookup);
}
// Case 2. current item becomes part of second subset
boolean B = false;
if (!A && (b - S[n] >= 0)) {
B = subsetSum(S, n - 1, a, b - S[n], c, lookup);
}
// Case 3. current item becomes part of third subset
boolean C = false;
if ((!A && !B) && (c - S[n] >= 0)) {
C = subsetSum(S, n - 1, a, b, c - S[n], lookup);
}
// return true if we get solution
lookup.put(key, A || B || C);
}
// return the subproblem solution from the map
return lookup.get(key);
}
// Function for solving 3-partition problem. It return true if given
// set S can be divided into three subsets with equal sum
public static boolean partition(int[] S)
{
if (S.length < 3) {
return false;
}
// create a map to store solutions of subproblems
Map<String, Boolean> lookup = new HashMap<>();
// get sum of all elements in the set
int sum = Arrays.stream(S).sum();
// return true if sum is divisble by 3 and the set can can
// be divided into three subsets with equal sum
return (sum % 3) == 0 && subsetSum(S, S.length - 1, sum/3,
sum/3, sum/3, lookup);
}
K Partition Problemhttp://www.geeksforgeeks.org/partition-set-k-subsets-equal-sum
Given an integer array of N elements, the task is to divide this array into K non-empty subsets such that the sum of elements in every subset is same. All elements of this array should be part of exactly one partition.
Input : arr = [2, 1, 4, 5, 6], K = 3 Output : Yes we can divide above array into 3 parts with equal sum as [[2, 4], [1, 5], [6]] Input : arr = [2, 1, 5, 5, 6], K = 3 Output : No It is not possible to divide above array into 3 parts with equal sum
http://www.techiedelight.com/k-partition-problem-print-all-subsets/
If sum is divisible by k, we check if k subsets with sum of elements equal to (sum/k) exists or not. We can find this by considering each item in the given array one by one and for each item we include it in the i’th subset & recurse for remaining items with remaining sum. We backtrack if solution is not found by including current item in i’th subset and try for (i+i)th subset.
We return true and print the subsets when k subsets each with zero sum are found. For printing the partitions, we maintain an separate array A[] to keep track of subsets elements. If the value of A[i] is k, then it means that i’th item of S is part of k’th subset.
// Function to check if all subsets are filled or not
bool checkSum(int sumLeft[], int k)
{
int r = true;
for (int i = 0; i < k; i++)
{
if (sumLeft[i] != 0)
r = false;
}
return r;
}
// Helper function for solving k partition problem
// It return true if there exists k subsets with given sum
bool subsetSum(int S[], int n, int sumLeft[], int A[], int k)
{
// return true if subset is found
if (checkSum(sumLeft, k))
return true;
// base case: no items left
if (n < 0)
return false;
bool res = false;
// consider current item S[n] and explore all possibilities
// using backtracking
for (int i = 0; i < k; i++)
{
if (!res && (sumLeft[i] - S[n]) >= 0)
{
// mark current element subset
A[n] = i + 1;
// add current item to i'th subset
sumLeft[i] = sumLeft[i] - S[n];
// recurse for remaining items
res = subsetSum(S, n - 1, sumLeft, A, k);
// backtrack - remove current item from i'th subset
sumLeft[i] = sumLeft[i] + S[n];
}
}
// return true if we get solution
return res;
}
// Function for solving k-partition problem. It prints the subsets if
// set S[0..n-1] can be divided into k subsets with equal sum
void partition(int S[], int n, int k)
{
// base case
if (n < k)
{
std::cout << "k-Partition of set S is not Possible";
return;
}
// get sum of all elements in the set
int sum = std::accumulate(S, S + n, 0);
int A[n], sumLeft[k];
// create an array of size k for each subset and initialize it
// by their expected sum i.e. sum/k
for (int i = 0; i < k; i++)
sumLeft[i] = sum/k;
// return true if sum is divisible by k and the set S can
// be divided into k subsets with equal sum
bool res = !(sum % k) && subsetSum(S, n - 1, sumLeft, A, k);
if (!res)
{
std::cout << "k-Partition of set S is not Possible";
return;
}
// print all k-partitions
for (int i = 0; i < k; i++)
{
std::cout << "Partition " << i << " is: ";
for (int j = 0; j < n; j++)
if (A[j] == i + 1)
std::cout << S[j] << " ";
std::cout << std::endl;
}
}
We can solve this problem recursively, we keep an array for sum of each partition and a boolean array to check whether an element is already taken into some partition or not.
First we need to check some base cases,
If K is 1, then we already have our answer, complete array is only subset with same sum.
If N < K, then it is not possible to divide array into subsets with equal sum, because we can’t divide the array into more than N parts.
If sum of array is not divisible by K, then it is not possible to divide the array. We will proceed only if k divides sum. Our goal reduces to divide array into K parts where sum of each part should be array_sum/K
In below code a recursive method is written which tries to add array element into some subset. If sum of this subset reaches required sum, we iterate for next part recursively, otherwise we backtrack for different set of elements. If number of subsets whose sum reaches the required sum is (K-1), we flag that it is possible to partition array into K parts with equal sum, because remaining elements already have a sum equal to required sum.
First we need to check some base cases,
If K is 1, then we already have our answer, complete array is only subset with same sum.
If N < K, then it is not possible to divide array into subsets with equal sum, because we can’t divide the array into more than N parts.
If sum of array is not divisible by K, then it is not possible to divide the array. We will proceed only if k divides sum. Our goal reduces to divide array into K parts where sum of each part should be array_sum/K
In below code a recursive method is written which tries to add array element into some subset. If sum of this subset reaches required sum, we iterate for next part recursively, otherwise we backtrack for different set of elements. If number of subsets whose sum reaches the required sum is (K-1), we flag that it is possible to partition array into K parts with equal sum, because remaining elements already have a sum equal to required sum.
bool isKPartitionPossibleRec(int arr[], int subsetSum[], bool taken[], int subset, int K, int N, int curIdx, int limitIdx){ if (subsetSum[curIdx] == subset) { /* current index (K - 2) represents (K - 1) subsets of equal sum last subsetition will already remain with sum 'subset'*/ if (curIdx == K - 2) return true; // recursive call for next subsetition return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx + 1, N - 1); } // start from limitIdx and include elements into current subsetition for (int i = limitIdx; i >= 0; i--) { // if already taken, continue if (taken[i]) continue; int tmp = subsetSum[curIdx] + arr[i]; // if temp is less than subset then only include the element // and call recursively if (tmp <= subset) { // mark the element and include into current subsetition sum taken[i] = true; subsetSum[curIdx] += arr[i]; bool nxt = isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, curIdx, i - 1); // after recursive call unmark the element and remove from // subsetition sum taken[i] = false; subsetSum[curIdx] -= arr[i]; if (nxt) return true; } } return false;}// Method returns true if arr can be subsetitioned into K subsets// with equal sumbool isKPartitionPossible(int arr[], int N, int K){ // If K is 1, then complete array will be our answer if (K == 1) return true; // If total number of subsetitions are more than N, then // division is not possible if (N < K) return false; // if array sum is not divisible by K then we can't divide // array into K subsetitions int sum = 0; for (int i = 0; i < N; i++) sum += arr[i]; if (sum % K != 0) return false; // the sum of each subset should be subset (= sum / K) int subset = sum / K; int subsetSum[K]; bool taken[N]; // Initialize sum of each subset from 0 for (int i = 0; i < K; i++) subsetSum[i] = 0; // mark all elements as not taken for (int i = 0; i < N; i++) taken[i] = false; // initialize first subsubset sum as last element of // array and mark that as taken subsetSum[0] = arr[N - 1]; taken[N - 1] = true; if (subset < subsetSum[0]) return false; // call recursive method to check K-subsetition condition return isKPartitionPossibleRec(arr, subsetSum, taken, subset, K, N, 0, N - 1);}