Check if an array can be split into 3 subsequences of equal sum or not

0 0 13 minutes read

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 not
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 max(max(l, m), r);
  }
}
 
// Function to check array can be
// partition to 3 subsequences of
// equal sum or not
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) 
  {
    cout << "Yes";
  }
  else
  {
    cout << "No";
  }
}
 
// Driver Code
int 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 approach
class GFG{
 
// Utility function to check array can
// be partition to 3 subsequences of
// equal sum or not
static 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 not
static 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 Code
public 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 call
checkEqualSum(arr, N)
 
# This code is contributed by Stuti Pathak

C#

// C# program for 
// the above approach
using System;
class GFG{
 
// Utility function to check array can
// be partition to 3 subsequences of
// equal sum or not
static 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 not
static 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 Code
public 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 not
function checkEqualSumUtil( arr,  N,
                             sm1,  sm2,
                             sm3,  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
    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 not
function checkEqualSum(arr,N)
{
// Initialise 3 sums to 0
let 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[]
let arr = [17, 34, 59, 23, 17,
            67, 57, 2, 18, 59, 1];    
 
let N = arr.length;
 
// Function Call
checkEqualSum(arr, N);
 
// This code is contributed by sravan kumar 
</script>

Output:

Yes

Time Complexity: O(3^N)
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 equal
int 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 not
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) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
}
 
// Driver Code
int 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 approach
import java.util.*;
class GFG{
static HashMap<String,
               Integer> dp = new HashMap<String,
                                         Integer>();
 
// Function to check array can be
// partition into sum of 3 equal
static 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 not
static 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 Code
public 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 approach
using 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 equal
static 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 not
static 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 Code
public 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 approach
var dp = new Map();
 
// Function to check array can be
// partition into sum of 3 equal
function 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 not
function 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 Call
checkEqualSum(arr, N);
 
 
</script>

Output:

Yes

Time Complexity: O(N*K²)
Auxiliary Space: O(N*K²) 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 zambiatek!