Partition of a set into K subsets with equal sum + 3|K Partition Problem


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/
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}
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 –
  1. We include the current item in the first subset and recurse for remaining items with remaining sum.
     
  2. We include the current item in the second subset and recurse for remaining items with remaining sum.
     
  3. 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 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.

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.
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 sum
bool 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);
}


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts