Given an array arr[] of integers, the task is to find all possible ways the array could be split into two subsequences such that the sum of the elements in both the subsequences is equal. Each number in the array must belong to only one of the two subsequences. Print all possible combinations of two subsequences.
Examples:
Input: arr[] = {1, 2, 3, 9, 4, 5}
Output:
1 2 9 and 3 4 5
1 2 4 5 and 3 9
3 9 and 1 2 4 5
3 4 5 and 1 2 9Input: arr[] = {4, -1, 2, -1}
Output:
4 -1 -1 and 2
2 and 4 -1 -1
Approach: A simple solution is to form all possible pairs of subsequences using recursion and compare the sum of elements in both the subsequences. For each array element, we have two choices, we can either take the current element in the first subsequence or the second.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define MAX 100000// Function to print the subsequence elementsvoid print(int g1[], int a, int g2[], int b){ // Prints elements of the 1st subarray for (int i = 0; i < a; i++) { cout << g1[i] << " "; } cout << "and "; // Prints elements of the 2nd subarray for (int i = 0; i < b; i++) { cout << g2[i] << " "; } cout << endl;}// Function that returns true if the sum of the// elements of arrays g1[] and g2[] is equalbool checksum(int g1[], int a, int g2[], int b){ int i, x; // Adding elements of the 1st array for (i = 0, x = 0; i < a; i++) { x += g1[i]; } // Subtracting elements of the 2nd array for (i = 0; i < b; i++) { x -= g2[i]; } // If x is 0 then the sum of elements // in both the arrays is equal return (x == 0);}// Function to find all valid subsequencesvoid formgroups(int arr[], int x, int g1[], int a, int g2[], int b, int n){ // Base Case if (x == n) { // If sum of the two subsequences // is equal then print the elements if (checksum(g1, a, g2, b)) { // Print the subsequences print(g1, a, g2, b); } return; } // Recursive Case // Choose current element to be a // part of the first subsequence g1[a] = arr[x]; formgroups(arr, x + 1, g1, a + 1, g2, b, n); // Choose current element to be a // part of the second subsequence g2[b] = arr[x]; formgroups(arr, x + 1, g1, a, g2, b + 1, n);}// Driver codeint main(){ int arr[] = { 1, 2, 3, 9, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); int g1[MAX], g2[MAX]; formgroups(arr, 0, g1, 0, g2, 0, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {static int MAX = 100000;// Function to print the // subsequence elementsstatic void print(int g1[], int a, int g2[], int b){ // Prints elements of the 1st subarray for (int i = 0; i < a; i++) { System.out.print(g1[i] + " "); } System.out.print("and "); // Prints elements of the 2nd subarray for (int i = 0; i < b; i++) { System.out.print(g2[i] + " "); } System.out.println();}// Function that returns true if // the sum of the elements of // arrays g1[] and g2[] is equalstatic boolean checksum(int g1[], int a, int g2[], int b){ int i, x; // Adding elements of the 1st array for (i = 0, x = 0; i < a; i++) { x += g1[i]; } // Subtracting elements of // the 2nd array for (i = 0; i < b; i++) { x -= g2[i]; } // If x is 0 then the sum of elements // in both the arrays is equal return (x == 0);}// Function to find all valid subsequencesstatic void formgroups(int arr[], int x, int g1[], int a, int g2[], int b, int n){ // Base Case if (x == n) { // If sum of the two subsequences // is equal then print the elements if (checksum(g1, a, g2, b)) { // Print the subsequences print(g1, a, g2, b); } return; } // Recursive Case // Choose current element to be a // part of the first subsequence g1[a] = arr[x]; formgroups(arr, x + 1, g1, a + 1, g2, b, n); // Choose current element to be a // part of the second subsequence g2[b] = arr[x]; formgroups(arr, x + 1, g1, a, g2, b + 1, n);}// Driver codepublic static void main(String[] args) { int arr[] = { 1, 2, 3, 9, 4, 5 }; int n = arr.length; int []g1 = new int[MAX]; int []g2 = new int[MAX]; formgroups(arr, 0, g1, 0, g2, 0, n);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python 3 implementation of the approachMAX = 100000# Function to print the subsequence elementsdef prints(g1, a, g2, b): # Prints elements of the 1st subarray for i in range(a): print(g1[i], end = " ") print("and ", end = "") # Prints elements of the 2nd subarray for i in range(b): print(g2[i], end = " ") print("\n", end = "")# Function that returns true if the sum of the# elements of arrays g1[] and g2[] is equaldef checksum(g1, a, g2, b): # Adding elements of the 1st array x = 0 for i in range(0, a, 1): x += g1[i] # Subtracting elements of the 2nd array for i in range(b): x -= g2[i] # If x is 0 then the sum of elements # in both the arrays is equal return (x == 0)# Function to find all valid subsequencesdef formgroups(arr, x, g1, a, g2, b, n): # Base Case if (x == n): # If sum of the two subsequences # is equal then print the elements if (checksum(g1, a, g2, b)): # Print the subsequences prints(g1, a, g2, b) return # Recursive Case # Choose current element to be a # part of the first subsequence g1[a] = arr[x] formgroups(arr, x + 1, g1, a + 1, g2, b, n) # Choose current element to be a # part of the second subsequence g2[b] = arr[x] formgroups(arr, x + 1, g1, a, g2, b + 1, n)# Driver codeif __name__ == '__main__': arr = [1, 2, 3, 9, 4, 5] n = len(arr) g1 = [0 for i in range(MAX)] g2 = [0 for i in range(MAX)] formgroups(arr, 0, g1, 0, g2, 0, n)# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG {static int MAX = 100000;// Function to print the // subsequence elementsstatic void print(int []g1, int a, int []g2, int b){ // Prints elements of the 1st subarray for (int i = 0; i < a; i++) { Console.Write(g1[i] + " "); } Console.Write("and "); // Prints elements of the 2nd subarray for (int i = 0; i < b; i++) { Console.Write(g2[i] + " "); } Console.WriteLine();}// Function that returns true if // the sum of the elements of // arrays g1[] and g2[] is equalstatic bool checksum(int []g1, int a, int []g2, int b){ int i, x; // Adding elements of the 1st array for (i = 0, x = 0; i < a; i++) { x += g1[i]; } // Subtracting elements of // the 2nd array for (i = 0; i < b; i++) { x -= g2[i]; } // If x is 0 then the sum of elements // in both the arrays is equal return (x == 0);}// Function to find all valid subsequencesstatic void formgroups(int []arr, int x, int []g1, int a, int []g2, int b, int n){ // Base Case if (x == n) { // If sum of the two subsequences // is equal then print the elements if (checksum(g1, a, g2, b)) { // Print the subsequences print(g1, a, g2, b); } return; } // Recursive Case // Choose current element to be a // part of the first subsequence g1[a] = arr[x]; formgroups(arr, x + 1, g1, a + 1, g2, b, n); // Choose current element to be a // part of the second subsequence g2[b] = arr[x]; formgroups(arr, x + 1, g1, a, g2, b + 1, n);}// Driver codepublic static void Main() { int []arr = { 1, 2, 3, 9, 4, 5 }; int n = arr.Length; int []g1 = new int[MAX]; int []g2 = new int[MAX]; formgroups(arr, 0, g1, 0, g2, 0, n);}}// This code is contributed by anuj_67... |
PHP
<?php// PHP implementation of the approachconst MAX = 100000; // Function to print the subsequence elements function printi($g1, $a, $g2, $b) { // Prints elements of the 1st subarray for ($i = 0; $i < $a; $i++) { echo ($g1[$i]); echo " "; } echo ("and "); // Prints elements of the 2nd subarray for ($i = 0; $i < $b; $i++) { echo ($g2[$i]); echo " "; } echo "\n"; } // Function that returns true if the sum of the // elements of arrays g1[] and g2[] is equal function checksum($g1, $a, $g2, $b) { // Adding elements of the 1st array for ($i = 0, $x = 0; $i < $a; $i++) { $x += $g1[$i]; } // Subtracting elements of the 2nd array for ($i = 0; $i < $b; $i++) { $x -= $g2[$i]; } // If x is 0 then the sum of elements // in both the arrays is equal return ($x == 0); } // Function to find all valid subsequences function formgroups($arr, $x, $g1, $a, $g2, $b, $n) { // Base Case if ($x == $n) { // If sum of the two subsequences // is equal then print the elements if (checksum($g1, $a, $g2, $b)) { // Print the subsequences printi($g1, $a, $g2, $b); } return; } // Recursive Case // Choose current element to be a // part of the first subsequence $g1[$a] = $arr[$x]; formgroups($arr, $x + 1, $g1, $a + 1, $g2, $b, $n); // Choose current element to be a // part of the second subsequence $g2[$b] = $arr[$x]; formgroups($arr, $x + 1, $g1, $a, $g2, $b + 1, $n); } // Driver code $arr = array(1, 2, 3, 9, 4, 5); $n = count($arr);$g1 = array();$g2 = array();formgroups($arr, 0, $g1, 0, $g2, 0, $n); // This code is contributed by Naman_Garg.?> |
Javascript
<script>// Javascript implementation of the approachvar MAX = 100000;// Function to print the subsequence elementsfunction print(g1, a, g2, b){ // Prints elements of the 1st subarray for(var i = 0; i < a; i++) { document.write( g1[i] + " "); } document.write("and "); // Prints elements of the 2nd subarray for(var i = 0; i < b; i++) { document.write( g2[i] + " "); } document.write("<br>");}// Function that returns true if the sum of the// elements of arrays g1[] and g2[] is equalfunction checksum(g1, a, g2, b){ var i, x; // Adding elements of the 1st array for(i = 0, x = 0; i < a; i++) { x += g1[i]; } // Subtracting elements of the 2nd array for(i = 0; i < b; i++) { x -= g2[i]; } // If x is 0 then the sum of elements // in both the arrays is equal return (x == 0);}// Function to find all valid subsequencesfunction formgroups(arr, x, g1, a, g2, b, n){ // Base Case if (x == n) { // If sum of the two subsequences // is equal then print the elements if (checksum(g1, a, g2, b)) { // Print the subsequences print(g1, a, g2, b); } return; } // Recursive Case // Choose current element to be a // part of the first subsequence g1[a] = arr[x]; formgroups(arr, x + 1, g1, a + 1, g2, b, n); // Choose current element to be a // part of the second subsequence g2[b] = arr[x]; formgroups(arr, x + 1, g1, a, g2, b + 1, n);}// Driver codevar arr = [ 1, 2, 3, 9, 4, 5 ];var n = arr.length;var g1 = Array(MAX).fill(0), g2 = Array(MAX).fill(0);formgroups(arr, 0, g1, 0, g2, 0, n);// This code is contributed by noob2000</script> |
Output:
1 2 9 and 3 4 5 1 2 4 5 and 3 9 3 9 and 1 2 4 5 3 4 5 and 1 2 9
Time Complexity: O(2n)
Auxiliary Space: O(n), where n is the length of the input array
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!
