Partition problem using recursion

To solve the problem follow the below idea:

Let isSubsetSum(arr, n, sum/2) be the function that returns true if there is a subset of arr[0..n-1] with sum equal to sum/2
The isSubsetSum problem can be divided into two subproblems

isSubsetSum() without considering last element (reducing n to n-1)

isSubsetSum considering the last element (reducing sum/2 by arr[n-1] and n to n-1)

If any of the above subproblems return true, then return true.
isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) || isSubsetSum (arr, n-1, sum/2 – arr[n-1])

Follow the below steps to solve the problem:

First, check if the sum of the elements is even or not
After checking, call the recursive function isSubsetSum with parameters as input array, array size, and sum/2
- If the sum is equal to zero then return true (Base case)
- If n is equal to 0 and sum is not equal to zero then return false (Base case)
- Check if the value of the last element is greater than the remaining sum then call this function again by removing the last element
- else call this function again for both the cases stated above and return true, if anyone of them returns true
Print the answer

Below is the implementation of the above approach:

C++

// A recursive C++ program for partition problem
#include <bits/stdc++.h>
using namespace std;
 
// A utility function that returns true if there is
// a subset of arr[] with sum equal to given sum
bool isSubsetSum(int arr[], int n, int sum)
{
    // Base Cases
    if (sum == 0)
        return true;
    if (n == 0 && sum != 0)
        return false;
 
    // If last element is greater than sum, then
    // ignore it
    if (arr[n - 1] > sum)
        return isSubsetSum(arr, n - 1, sum);
 
    /* else, check if sum can be obtained by any of
        the following
        (a) including the last element
        (b) excluding the last element
    */
    return isSubsetSum(arr, n - 1, sum)
           || isSubsetSum(arr, n - 1, sum - arr[n - 1]);
}
 
// Returns true if arr[] can be partitioned in two
// subsets of equal sum, otherwise false
bool findPartiion(int arr[], int n)
{
    // Calculate sum of the elements in array
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    // If sum is odd, there cannot be two subsets
    // with equal sum
    if (sum % 2 != 0)
        return false;
 
    // Find if there is subset with sum equal to
    // half of total sum
    return isSubsetSum(arr, n, sum / 2);
}
 
// Driver code
int main()
{
    int arr[] = { 3, 1, 5, 9, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    if (findPartiion(arr, n) == true)
        cout << "Can be divided into two subsets "
                "of equal sum";
    else
        cout << "Can not be divided into two subsets"
                " of equal sum";
    return 0;
}
 
// This code is contributed by rathbhupendra

C

// A recursive C program for partition problem
#include <stdbool.h>
#include <stdio.h>
 
// A utility function that returns true if there is
// a subset of arr[] with sum equal to given sum
bool isSubsetSum(int arr[], int n, int sum)
{
    // Base Cases
    if (sum == 0)
        return true;
    if (n == 0 && sum != 0)
        return false;
 
    // If last element is greater than sum, then
    // ignore it
    if (arr[n - 1] > sum)
        return isSubsetSum(arr, n - 1, sum);
 
    /* else, check if sum can be obtained by any of
       the following
       (a) including the last element
       (b) excluding the last element
    */
    return isSubsetSum(arr, n - 1, sum)
           || isSubsetSum(arr, n - 1, sum - arr[n - 1]);
}
 
// Returns true if arr[] can be partitioned in two
//  subsets of equal sum, otherwise false
bool findPartiion(int arr[], int n)
{
    // Calculate sum of the elements in array
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    // If sum is odd, there cannot be two subsets
    // with equal sum
    if (sum % 2 != 0)
        return false;
 
    // Find if there is subset with sum equal to
    // half of total sum
    return isSubsetSum(arr, n, sum / 2);
}
 
// Driver code
int main()
{
    int arr[] = { 3, 1, 5, 9, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    if (findPartiion(arr, n) == true)
        printf("Can be divided into two subsets "
               "of equal sum");
    else
        printf("Can not be divided into two subsets"
               " of equal sum");
    return 0;
}

Java

// A recursive Java solution for partition problem
import java.io.*;
 
class Partition {
    // A utility function that returns true if there is a
    // subset of arr[] with sum equal to given sum
    static boolean isSubsetSum(int arr[], int n, int sum)
    {
        // Base Cases
        if (sum == 0)
            return true;
        if (n == 0 && sum != 0)
            return false;
 
        // If last element is greater than sum, then ignore
        // it
        if (arr[n - 1] > sum)
            return isSubsetSum(arr, n - 1, sum);
 
        /* else, check if sum can be obtained by any of
           the following
        (a) including the last element
        (b) excluding the last element
        */
        return isSubsetSum(arr, n - 1, sum)
            || isSubsetSum(arr, n - 1, sum - arr[n - 1]);
    }
 
    // Returns true if arr[] can be partitioned in two
    // subsets of equal sum, otherwise false
    static boolean findPartition(int arr[], int n)
    {
        // Calculate sum of the elements in array
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += arr[i];
 
        // If sum is odd, there cannot be two subsets
        // with equal sum
        if (sum % 2 != 0)
            return false;
 
        // Find if there is subset with sum equal to half
        // of total sum
        return isSubsetSum(arr, n, sum / 2);
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        int arr[] = { 3, 1, 5, 9, 12 };
        int n = arr.length;
 
        // Function call
        if (findPartition(arr, n) == true)
            System.out.println("Can be divided into two "
                               + "subsets of equal sum");
        else
            System.out.println(
                "Can not be divided into "
                + "two subsets of equal sum");
    }
}
/* This code is contributed by Devesh Agrawal */

Python3

# A recursive Python3 program for
# partition problem
 
# A utility function that returns
# true if there is a subset of
# arr[] with sum equal to given sum
 
 
def isSubsetSum(arr, n, sum):
    # Base Cases
    if sum == 0:
        return True
    if n == 0 and sum != 0:
        return False
 
    # If last element is greater than sum, then
    # ignore it
    if arr[n-1] > sum:
        return isSubsetSum(arr, n-1, sum)
 
    ''' else, check if sum can be obtained by any of 
    the following
    (a) including the last element
    (b) excluding the last element'''
 
    return isSubsetSum(arr, n-1, sum) or isSubsetSum(arr, n-1, sum-arr[n-1])
 
# Returns true if arr[] can be partitioned in two
# subsets of equal sum, otherwise false
 
 
def findPartion(arr, n):
    # Calculate sum of the elements in array
    sum = 0
    for i in range(0, n):
        sum += arr[i]
    # If sum is odd, there cannot be two subsets
    # with equal sum
    if sum % 2 != 0:
        return false
 
    # Find if there is subset with sum equal to
    # half of total sum
    return isSubsetSum(arr, n, sum // 2)
 
 
# Driver code
if __name__ == '__main__':
  arr = [3, 1, 5, 9, 12]
  n = len(arr)
 
  # Function call
  if findPartion(arr, n) == True:
      print("Can be divided into two subsets of equal sum")
  else:
      print("Can not be divided into two subsets of equal sum")
 
# This code is contributed by shreyanshi_arun.

C#

// A recursive C# solution for partition problem
using System;
 
class GFG {
 
    // A utility function that returns true if there is a
    // subset of arr[] with sum equal to given sum
    static bool isSubsetSum(int[] arr, int n, int sum)
    {
        // Base Cases
        if (sum == 0)
            return true;
        if (n == 0 && sum != 0)
            return false;
 
        // If last element is greater than sum, then ignore
        // it
        if (arr[n - 1] > sum)
            return isSubsetSum(arr, n - 1, sum);
 
        /* else, check if sum can be obtained by any of
        the following
        (a) including the last element
        (b) excluding the last element
        */
        return isSubsetSum(arr, n - 1, sum)
            || isSubsetSum(arr, n - 1, sum - arr[n - 1]);
    }
 
    // Returns true if arr[] can be partitioned in two
    // subsets of equal sum, otherwise false
    static bool findPartition(int[] arr, int n)
    {
        // Calculate sum of the elements in array
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += arr[i];
 
        // If sum is odd, there cannot be two subsets
        // with equal sum
        if (sum % 2 != 0)
            return false;
 
        // Find if there is subset with sum equal to half
        // of total sum
        return isSubsetSum(arr, n, sum / 2);
    }
 
    // Driver code
    public static void Main()
    {
 
        int[] arr = { 3, 1, 5, 9, 12 };
        int n = arr.Length;
 
        // Function call
        if (findPartition(arr, n) == true)
            Console.Write("Can be divided into two "
                          + "subsets of equal sum");
        else
            Console.Write("Can not be divided into "
                          + "two subsets of equal sum");
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// A recursive PHP solution for partition problem
 
// A utility function that returns true if there is 
// a subset of arr[] with sum equal to given sum 
function isSubsetSum ($arr, $n, $sum) 
{ 
    // Base Cases 
    if ($sum == 0) 
        return true; 
    if ($n == 0 && $sum != 0) 
        return false; 
     
    // If last element is greater than 
    // sum, then ignore it 
    if ($arr[$n - 1] > $sum) 
        return isSubsetSum ($arr, $n - 1, $sum); 
     
    /* else, check if sum can be obtained 
       by any of the following 
        (a) including the last element 
        (b) excluding the last element 
    */
    return isSubsetSum ($arr, $n - 1, $sum) || 
           isSubsetSum ($arr, $n - 1, 
                        $sum - $arr[$n - 1]); 
}  
 
// Returns true if arr[] can be partitioned 
// in two subsets of equal sum, otherwise false 
function findPartiion ($arr, $n) 
{ 
    // Calculate sum of the elements
    // in array 
    $sum = 0; 
    for ($i = 0; $i < $n; $i++) 
    $sum += $arr[$i]; 
 
    // If sum is odd, there cannot be 
    // two subsets with equal sum 
    if ($sum % 2 != 0) 
    return false; 
 
    // Find if there is subset with sum
    // equal to half of total sum 
    return isSubsetSum ($arr, $n, $sum / 2); 
} 
 
// Driver Code
$arr = array(3, 1, 5, 9, 12); 
$n = count($arr); 
 
// Function call
if (findPartiion($arr, $n) == true) 
    echo "Can be divided into two subsets of equal sum"; 
else
    echo "Can not be divided into two subsets of equal sum"; 
 
// This code is contributed by rathbhupendra
?>

Javascript

<script>
// A recursive Javascript solution for partition problem
     
    // A utility function that returns true if there is a
    // subset of arr[] with sum equal to given sum
    function isSubsetSum(arr,n,sum)
    {
        // Base Cases
        if (sum == 0)
            return true;
        if (n == 0 && sum != 0)
            return false;
  
        // If last element is greater than sum, then ignore
        // it
        if (arr[n - 1] > sum)
            return isSubsetSum(arr, n - 1, sum);
  
        /* else, check if sum can be obtained by any of
           the following
        (a) including the last element
        (b) excluding the last element
        */
        return isSubsetSum(arr, n - 1, sum)
            || isSubsetSum(arr, n - 1, sum - arr[n - 1]);
    }
     
    // Returns true if arr[] can be partitioned in two
    // subsets of equal sum, otherwise false
    function findPartition(arr,n)
    {
        // Calculate sum of the elements in array
        let sum = 0;
        for (let i = 0; i < n; i++)
            sum += arr[i];
  
        // If sum is odd, there cannot be two subsets
        // with equal sum
        if (sum % 2 != 0)
            return false;
  
        // Find if there is subset with sum equal to half
        // of total sum
        return isSubsetSum(arr, n, Math.floor(sum / 2));
    }
     
    // Driver code
    let arr=[3, 1, 5, 9, 12 ];
    let n = arr.length;
    // Function call
    if (findPartition(arr, n) == true)
        document.write("Can be divided into two "
                               + "subsets of equal sum");
    else
        document.write(
                "Can not be divided into "
                + "two subsets of equal sum");
     
    // This code is contributed by unknown2108
</script>

Output

Can be divided into two subsets of equal sum

Time Complexity: O(2^N) In the worst case, this solution tries two possibilities (whether to include or exclude) for every element.
Auxiliary Space: O(N). Recursion stack space

Partition problem using recursion

C++

C

Java

Python3

C#

PHP

Javascript

Partition problem | DP-18

Categories

Contact US

Partition problem using recursion

C++

C

Java

Python3

C#

PHP

Javascript

Partition problem | DP-18

Similar Reads

Categories

Contact US