Given an array arr[] having N integers. The task is to determine if the array can be partitioned into 3 subsequences of an equal sum or not. If yes then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {1, 1, 1}
Output: Yes
Explanation:
Here array can be partition into 3 equal sum. {1}Input: arr[] = {40}
Output: No
Explanation:
Here array cannot be partition into 3 equal sum.
Recursive Approach: This problem can be solved using recursion. Below are the steps:
- Initialize three variable sum1, sum2, and sum3 to value 0.
- Then every element of array arr[] is added to either of these 3 variables, which give all the possible combinations.
- In case, any subsequences having 3 equal sums then the array can be partition.
- If the array can be partition then print “Yes” else print “No”.
C++
// C++ program for // the above approach#include <bits/stdc++.h>using namespace std;// Utility function to check array can// be partition to 3 subsequences of// equal sum or notint checkEqualSumUtil(int arr[], int N, int sm1, int sm2, int sm3, int j){ // Base Case if (j == N) { if (sm1 == sm2 && sm2 == sm3) return 1; else return 0; } else { // When element at index // j is added to sm1 int l = checkEqualSumUtil(arr, N, sm1 + arr[j], sm2, sm3, j + 1); // When element at index // j is added to sm2 int m = checkEqualSumUtil(arr, N, sm1, sm2 + arr[j], sm3, j + 1); // When element at index // j is added to sm3 int r = checkEqualSumUtil(arr, N, sm1, sm2, sm3 + arr[j], j + 1); // Return maximum value among // all above 3 recursive call return max(max(l, m), r); }}// Function to check array can be// partition to 3 subsequences of// equal sum or notvoid checkEqualSum(int arr[], int N){ // Initialise 3 sums to 0 int sum1, sum2, sum3; sum1 = sum2 = sum3 = 0; // Function Call if (checkEqualSumUtil(arr, N, sum1, sum2, sum3, 0)== 1) { cout << "Yes"; } else { cout << "No"; }}// Driver Codeint main(){ // Given array arr[] int arr[] = {17, 34, 59, 23, 17, 67, 57, 2, 18, 59, 1 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call checkEqualSum(arr, N); return 0;} |
Java
// Java program for // the above approachclass GFG{// Utility function to check array can// be partition to 3 subsequences of// equal sum or notstatic int checkEqualSumUtil(int arr[], int N, int sm1, int sm2, int sm3, int j){ // Base Case if (j == N) { if (sm1 == sm2 && sm2 == sm3) return 1; else return 0; } else { // When element at index // j is added to sm1 int l = checkEqualSumUtil(arr, N, sm1 + arr[j], sm2, sm3, j + 1); // When element at index // j is added to sm2 int m = checkEqualSumUtil(arr, N, sm1, sm2 + arr[j], sm3, j + 1); // When element at index // j is added to sm3 int r = checkEqualSumUtil(arr, N, sm1, sm2, sm3 + arr[j], j + 1); // Return maximum value among // all above 3 recursive call return Math.max(Math.max(l, m), r); }}// Function to check array can be// partition to 3 subsequences of// equal sum or notstatic void checkEqualSum(int arr[], int N){ // Initialise 3 sums to 0 int sum1, sum2, sum3; sum1 = sum2 = sum3 = 0; // Function Call if (checkEqualSumUtil(arr, N, sum1, sum2, sum3, 0) == 1) { System.out.print("Yes"); } else { System.out.print("No"); }}// Driver Codepublic static void main(String[] args){ // Given array arr[] int arr[] = {17, 34, 59, 23, 17, 67, 57, 2, 18, 59, 1}; int N = arr.length; // Function Call checkEqualSum(arr, N);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach # Utility function to check array can # be partition to 3 subsequences of # equal sum or not def checkEqualSumUtil(arr, N, sm1, sm2, sm3, j): # Base case if j == N: if sm1 == sm2 and sm2 == sm3: return 1 else: return 0 else: # When element at index # j is added to sm1 l = checkEqualSumUtil(arr, N, sm1 + arr[j], sm2, sm3, j + 1) # When element at index # j is added to sm2 m = checkEqualSumUtil(arr, N, sm1, sm2 + arr[j], sm3, j + 1) # When element at index # j is added to sm3 r = checkEqualSumUtil(arr, N, sm1, sm2, sm3 + arr[j], j + 1) # Return maximum value among # all above 3 recursive call return max(l, m, r) # Function to check array can be # partition to 3 subsequences of # equal sum or not def checkEqualSum(arr, N): # Initialise 3 sums to 0 sum1 = sum2 = sum3 = 0 # Function call if checkEqualSumUtil(arr, N, sum1, sum2, sum3, 0) == 1: print("Yes") else: print("No") # Driver code # Given array arr[] arr = [ 17, 34, 59, 23, 17, 67, 57, 2, 18, 59, 1 ]N = len(arr)# Function callcheckEqualSum(arr, N)# This code is contributed by Stuti Pathak |
C#
// C# program for // the above approachusing System;class GFG{// Utility function to check array can// be partition to 3 subsequences of// equal sum or notstatic int checkEqualSumUtil(int[] arr, int N, int sm1, int sm2, int sm3, int j){ // Base Case if (j == N) { if (sm1 == sm2 && sm2 == sm3) return 1; else return 0; } else { // When element at index // j is added to sm1 int l = checkEqualSumUtil(arr, N, sm1 + arr[j], sm2, sm3, j + 1); // When element at index // j is added to sm2 int m = checkEqualSumUtil(arr, N, sm1, sm2 + arr[j], sm3, j + 1); // When element at index // j is added to sm3 int r = checkEqualSumUtil(arr, N, sm1, sm2, sm3 + arr[j], j + 1); // Return maximum value among // all above 3 recursive call return Math.Max(Math.Max(l, m), r); }}// Function to check array can be// partition to 3 subsequences of// equal sum or notstatic void checkEqualSum(int[] arr, int N){ // Initialise 3 sums to 0 int sum1, sum2, sum3; sum1 = sum2 = sum3 = 0; // Function Call if (checkEqualSumUtil(arr, N, sum1, sum2, sum3, 0) == 1) { Console.Write("Yes"); } else { Console.Write("No"); }}// Driver Codepublic static void Main(){ // Given array arr[] int[] arr = {17, 34, 59, 23, 17, 67, 57, 2, 18, 59, 1}; int N = arr.Length; // Function Call checkEqualSum(arr, N);}}// This code is contributed by Chitranayal |
Javascript
<script>// Java script program for// the above approach// Utility function to check array can// be partition to 3 subsequences of// equal sum or notfunction checkEqualSumUtil( arr, N, sm1, sm2, sm3, j){// Base Caseif (j == N){ if (sm1 == sm2 && sm2 == sm3) return 1; else return 0;}else{ // When element at index // j is added to sm1 let l = checkEqualSumUtil(arr, N, sm1 + arr[j], sm2, sm3, j + 1); // When element at index // j is added to sm2 let m = checkEqualSumUtil(arr, N, sm1, sm2 + arr[j], sm3, j + 1); // When element at index // j is added to sm3 let r = checkEqualSumUtil(arr, N, sm1, sm2, sm3 + arr[j], j + 1); // Return maximum value among // all above 3 recursive call return Math.max(Math.max(l, m), r);}}// Function to check array can be// partition to 3 subsequences of// equal sum or notfunction checkEqualSum(arr,N){// Initialise 3 sums to 0let sum1, sum2, sum3;sum1 = sum2 = sum3 = 0;// Function Callif (checkEqualSumUtil(arr, N, sum1, sum2, sum3, 0) == 1){ document.write("Yes");}else{ document.write("No");}}// Driver Code// Given array arr[]let arr = [17, 34, 59, 23, 17, 67, 57, 2, 18, 59, 1]; let N = arr.length;// Function CallcheckEqualSum(arr, N);// This code is contributed by sravan kumar </script> |
Output:
Yes
Time Complexity: O(3N)
Auxiliary Space: O(1)
Dynamic Programming Approach: This problem can be solved using dynamic programming, the idea is to store all the overlapping subproblems value in a map and use the value of overlapping substructure to reduce the number of the recursive calls. Below are the steps:
- Let sum1, sum2, and sum3 be the three equal sum to be partitioned.
- Create a map dp having the key.
- Traverse the given array and do the following:
- Base Case: While traversing the array if we reach the end of the array then check if the value of sum1, sum2, and sum3 are equal then return 1 that will ensure that we can break the given array into a subsequence of equal sum value. Otherwise, return 0.
- Recursive Call: For each element in the array include each element in sum1, sum2, and sum3 one by one and return the maximum of these recursive calls.
a = recursive_function(arr, N, sum1 + arr[j], sum2, sum3, j + 1)
b = recursive_function(arr, N, sum1, sum2 + arr[j], sum3, j + 1)
c = recursive_function(arr, N, sum1, sum2, sum3 + arr[j], j + 1)
- Return Statement: In the above recursive call the maximum of the three values will give the result for the current recursive call. Update the current state in the dp table as:
string s = to_string(sum1) + ‘_’ + to_string(sum2) + to_string(j)
return dp[s] = max(a, max(b, c) )
- If there can be partition possible then print “Yes” else print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;map<string, int> dp;// Function to check array can be// partition into sum of 3 equalint checkEqualSumUtil(int arr[], int N, int sm1, int sm2, int sm3, int j){ string s = to_string(sm1) + "_" + to_string(sm2) + to_string(j); // Base Case if (j == N) { if (sm1 == sm2 && sm2 == sm3) return 1; else return 0; } // If value at particular index is not // -1 then return value at that index // which ensure no more further calls if (dp.find(s) != dp.end()) return dp[s]; else { // When element at index // j is added to sm1 int l = checkEqualSumUtil( arr, N, sm1 + arr[j], sm2, sm3, j + 1); // When element at index // j is added to sm2 int m = checkEqualSumUtil( arr, N, sm1, sm2 + arr[j], sm3, j + 1); // When element at index // j is added to sm3 int r = checkEqualSumUtil( arr, N, sm1, sm2, sm3 + arr[j], j + 1); // Update the current state and // return that value return dp[s] = max(max(l, m), r); }}// Function to check array can be// partition to 3 subsequences of// equal sum or notvoid checkEqualSum(int arr[], int N){ // Initialise 3 sums to 0 int sum1, sum2, sum3; sum1 = sum2 = sum3 = 0; // Function Call if (checkEqualSumUtil( arr, N, sum1, sum2, sum3, 0) == 1) { cout << "Yes"; } else { cout << "No"; }}// Driver Codeint main(){ // Given array arr[] int arr[] = { 17, 34, 59, 23, 17, 67, 57, 2, 18, 59, 1 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call checkEqualSum(arr, N); return 0;} |
Java
// Java program for // the above approachimport java.util.*;class GFG{static HashMap<String, Integer> dp = new HashMap<String, Integer>();// Function to check array can be// partition into sum of 3 equalstatic int checkEqualSumUtil(int arr[], int N, int sm1, int sm2, int sm3, int j){ String s = String.valueOf(sm1) + "_" + String.valueOf(sm2) + String.valueOf(j); // Base Case if (j == N) { if (sm1 == sm2 && sm2 == sm3) return 1; else return 0; } // If value at particular index is not // -1 then return value at that index // which ensure no more further calls if (dp.containsKey(s)) return dp.get(s); else { // When element at index // j is added to sm1 int l = checkEqualSumUtil(arr, N, sm1 + arr[j], sm2, sm3, j + 1); // When element at index // j is added to sm2 int m = checkEqualSumUtil(arr, N, sm1, sm2 + arr[j], sm3, j + 1); // When element at index // j is added to sm3 int r = checkEqualSumUtil(arr, N, sm1, sm2, sm3 + arr[j], j + 1); // Update the current state and // return that value dp.put(s, Math.max(Math.max(l, m), r)); return dp.get(s); }}// Function to check array can be// partition to 3 subsequences of// equal sum or notstatic void checkEqualSum(int arr[], int N){ // Initialise 3 sums to 0 int sum1, sum2, sum3; sum1 = sum2 = sum3 = 0; // Function Call if (checkEqualSumUtil(arr, N, sum1, sum2, sum3, 0) == 1) { System.out.print("Yes"); } else { System.out.print("No"); }}// Driver Codepublic static void main(String[] args){ // Given array arr[] int arr[] = {17, 34, 59, 23, 17, 67, 57, 2, 18, 59, 1}; int N = arr.length; // Function Call checkEqualSum(arr, N);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach dp = {}# Function to check array can be # partition into sum of 3 equal def checkEqualSumUtil(arr, N, sm1, sm2, sm3, j): s = str(sm1) + "_" + str(sm2) + str(j) # Base Case if j == N: if sm1 == sm2 and sm2 == sm3: return 1 else: return 0 # If value at particular index is not # -1 then return value at that index # which ensure no more further calls if s in dp: return dp[s] # When element at index # j is added to sm1 l = checkEqualSumUtil(arr, N, sm1 + arr[j], sm2, sm3, j + 1) # When element at index # j is added to sm2 m = checkEqualSumUtil(arr, N, sm1, sm2 + arr[j], sm3, j + 1) # When element at index # j is added to sm3 r = checkEqualSumUtil(arr, N, sm1, sm2, sm3 + arr[j], j + 1) # Update the current state and # return that value dp[s] = max(l, m, r) return dp[s]# Function to check array can be # partition to 3 subsequences of # equal sum or not def checkEqualSum(arr, N): # Initialise 3 sums to 0 sum1 = sum2 = sum3 = 0 # Function Call if checkEqualSumUtil(arr, N, sum1, sum2, sum3, 0) == 1: print("Yes") else: print("No") # Driver code# Given array arr[] arr = [ 17, 34, 59, 23, 17, 67, 57, 2, 18, 59, 1 ]N = len(arr)# Function call checkEqualSum(arr, N)# This code is contributed by Stuti Pathak |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ static Dictionary<string, int> dp = new Dictionary<string, int>(); // Function to check array can be// partition into sum of 3 equalstatic int checkEqualSumUtil(int []arr, int N, int sm1, int sm2, int sm3, int j){ string s = sm1.ToString() + "_" + sm2.ToString() + j.ToString(); // Base Case if (j == N) { if (sm1 == sm2 && sm2 == sm3) return 1; else return 0; } // If value at particular index is not // -1 then return value at that index // which ensure no more further calls if (dp.ContainsKey(s)) return dp[s]; else { // When element at index // j is added to sm1 int l = checkEqualSumUtil(arr, N, sm1 + arr[j], sm2, sm3, j + 1); // When element at index // j is added to sm2 int m = checkEqualSumUtil(arr, N, sm1, sm2 + arr[j], sm3, j + 1); // When element at index // j is added to sm3 int r = checkEqualSumUtil(arr, N, sm1, sm2, sm3 + arr[j], j + 1); // Update the current state and // return that value dp[s] = Math.Max(Math.Max(l, m), r); return dp[s]; }} // Function to check array can be// partition to 3 subsequences of// equal sum or notstatic void checkEqualSum(int []arr, int N){ // Initialise 3 sums to 0 int sum1, sum2, sum3; sum1 = sum2 = sum3 = 0; // Function call if (checkEqualSumUtil(arr, N, sum1, sum2, sum3, 0) == 1) { Console.Write("Yes"); } else { Console.Write("No"); }} // Driver Codepublic static void Main(string[] args){ // Given array arr[] int []arr = { 17, 34, 59, 23, 17, 67, 57, 2, 18, 59, 1 }; int N = arr.Length; // Function call checkEqualSum(arr, N);}}// This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript program for the above approachvar dp = new Map();// Function to check array can be// partition into sum of 3 equalfunction checkEqualSumUtil(arr, N, sm1, sm2, sm3, j){ var s = (sm1.toString()) + "_" + (sm2.toString()) + (j.toString()); // Base Case if (j == N) { if (sm1 == sm2 && sm2 == sm3) return 1; else return 0; } // If value at particular index is not // -1 then return value at that index // which ensure no more further calls if (dp.has(s)) return dp[s]; else { // When element at index // j is added to sm1 var l = checkEqualSumUtil( arr, N, sm1 + arr[j], sm2, sm3, j + 1); // When element at index // j is added to sm2 var m = checkEqualSumUtil( arr, N, sm1, sm2 + arr[j], sm3, j + 1); // When element at index // j is added to sm3 var r = checkEqualSumUtil( arr, N, sm1, sm2, sm3 + arr[j], j + 1); // Update the current state and // return that value return dp[s] = Math.max(Math.max(l, m), r); }}// Function to check array can be// partition to 3 subsequences of// equal sum or notfunction checkEqualSum(arr, N){ // Initialise 3 sums to 0 var sum1, sum2, sum3; sum1 = sum2 = sum3 = 0; // Function Call if (checkEqualSumUtil( arr, N, sum1, sum2, sum3, 0) == 1) { document.write( "Yes"); } else { document.write( "No"); }}// Driver Code// Given array arr[]var arr = [17, 34, 59, 23, 17, 67, 57, 2, 18, 59, 1];var N = arr.length;// Function CallcheckEqualSum(arr, N);</script> |
Output:
Yes
Time Complexity: O(N*K2)
Auxiliary Space: O(N*K2) where K is the sum of the array.
(to_string(sum1) + “_” + to_string(sum2) + “_” + to_string(sum3))
- with value is 1 if 3 equal subsets are found else value is 0.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
