Divida la array en partes de sumas iguales de acuerdo con las condiciones dadas

Dada una array de enteros arr[] , la tarea es verificar si la array de entrada se puede dividir en dos sub-arrays de manera que: 
 

• La suma de ambos sub-arreglos es igual.
• Todos los elementos que son divisibles por 5 deben estar en el mismo grupo.
• Todos los elementos que son divisibles por 3 (pero no por 5) deben estar en el otro grupo.
• Los elementos que no son divisibles por 5 ni por 3 se pueden poner en cualquier grupo.

Si es posible, imprima Sí ; de lo contrario, imprima No.
Ejemplos: 
 

Entrada: arr[] = {1, 2} 
Salida: No 
Los elementos no se pueden dividir en grupos de manera que la suma sea igual.
Entrada: arr[] = {1, 4, 3} 
Salida: Sí 
{1, 3} y {4} son los grupos que cumplen la condición dada. 
 

Enfoque: podemos usar un enfoque recursivo manteniendo la suma izquierda y la suma derecha para mantener dos grupos diferentes. La suma izquierda es para múltiplos de 5 y la suma derecha es para múltiplos de 3 (que no son múltiplos de 5) y los elementos que no son divisibles por 5 ni por 3 pueden estar en cualquier grupo que satisfaga la regla de igual suma (inclúyalos en la izquierda suma y suma correcta uno por uno).
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Recursive function that returns true if the array
// can be divided into two sub-arrays
// satisfying the given condition
bool helper(int* arr, int n, int start, int lsum, int rsum)
{
 
    // If reached the end
    if (start == n)
        return lsum == rsum;
 
    // If divisible by 5 then add to the left sum
    if (arr[start] % 5 == 0)
        lsum += arr[start];
 
    // If divisible by 3 but not by 5
    // then add to the right sum
    else if (arr[start] % 3 == 0)
        rsum += arr[start];
 
    // Else it can be added to any of the sub-arrays
    else
 
        // Try adding in both the sub-arrays (one by one)
        // and check whether the condition satisfies
        return helper(arr, n, start + 1, lsum + arr[start], rsum)
           || helper(arr, n, start + 1, lsum, rsum + arr[start]);
 
    // For cases when element is multiple of 3 or 5.
    return helper(arr, n, start + 1, lsum, rsum);
}
 
// Function to start the recursive calls
bool splitArray(int* arr, int n)
{
    // Initially start, lsum and rsum will all be 0
    return helper(arr, n, 0, 0, 0);
}
 
// Driver code
int main()
{
    int arr[] = { 1, 4, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    if (splitArray(arr, n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation of the approach
class Solution
{
 
// Recursive function that returns true if the array
// can be divided into two sub-arrays
// satisfying the given condition
static boolean helper(int arr[], int n,
                    int start, int lsum, int rsum)
{
 
    // If reached the end
    if (start == n)
        return lsum == rsum;
 
    // If divisible by 5 then add to the left sum
    if (arr[start] % 5 == 0)
        lsum += arr[start];
 
    // If divisible by 3 but not by 5
    // then add to the right sum
    else if (arr[start] % 3 == 0)
        rsum += arr[start];
 
    // Else it can be added to any of the sub-arrays
    else
 
        // Try adding in both the sub-arrays (one by one)
        // and check whether the condition satisfies
        return helper(arr, n, start + 1, lsum + arr[start], rsum)
        || helper(arr, n, start + 1, lsum, rsum + arr[start]);
 
    // For cases when element is multiple of 3 or 5.
    return helper(arr, n, start + 1, lsum, rsum);
}
 
// Function to start the recursive calls
static boolean splitArray(int arr[], int n)
{
    // Initially start, lsum and rsum will all be 0
    return helper(arr, n, 0, 0, 0);
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 1, 4, 3 };
    int n = arr.length;
 
    if (splitArray(arr, n))
        System.out.println( "Yes");
    else
        System.out.println( "No");
}
}
 
// This code is contributed by Arnab Kundu

# Python 3 implementation of the approach
 
# Recursive function that returns true if
# the array can be divided into two sub-arrays
# satisfying the given condition
def helper(arr, n, start, lsum, rsum):
 
    # If reached the end
    if (start == n):
        return lsum == rsum
 
    # If divisible by 5 then add
    # to the left sum
    if (arr[start] % 5 == 0):
        lsum += arr[start]
 
    # If divisible by 3 but not by 5
    # then add to the right sum
    elif (arr[start] % 3 == 0):
        rsum += arr[start]
 
    # Else it can be added to any of
    # the sub-arrays
    else:
 
        # Try adding in both the sub-arrays
        # (one by one) and check whether
        # the condition satisfies
        return (helper(arr, n, start + 1,
                lsum + arr[start], rsum) or
                helper(arr, n, start + 1,
                lsum, rsum + arr[start]));
 
    # For cases when element is multiple of 3 or 5.
    return helper(arr, n, start + 1, lsum, rsum)
 
# Function to start the recursive calls
def splitArray(arr, n):
     
    # Initially start, lsum and rsum
    # will all be 0
    return helper(arr, n, 0, 0, 0)
 
# Driver code
if __name__ == "__main__":
     
    arr = [ 1, 4, 3 ]
    n = len(arr)
 
    if (splitArray(arr, n)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by ita_c

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Recursive function that returns true if the array
    // can be divided into two sub-arrays
    // satisfying the given condition
    static bool helper(int []arr, int n,
                        int start, int lsum, int rsum)
    {
     
        // If reached the end
        if (start == n)
            return lsum == rsum;
     
        // If divisible by 5 then add to the left sum
        if (arr[start] % 5 == 0)
            lsum += arr[start];
     
        // If divisible by 3 but not by 5
        // then add to the right sum
        else if (arr[start] % 3 == 0)
            rsum += arr[start];
     
        // Else it can be added to any of the sub-arrays
        else
     
            // Try adding in both the sub-arrays (one by one)
            // and check whether the condition satisfies
            return helper(arr, n, start + 1, lsum + arr[start], rsum)
            || helper(arr, n, start + 1, lsum, rsum + arr[start]);
     
        // For cases when element is multiple of 3 or 5.
        return helper(arr, n, start + 1, lsum, rsum);
    }
     
    // Function to start the recursive calls
    static bool splitArray(int []arr, int n)
    {
        // Initially start, lsum and rsum will all be 0
        return helper(arr, n, 0, 0, 0);
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = { 1, 4, 3 };
        int n = arr.Length;
     
        if (splitArray(arr, n))
            Console.WriteLine( "Yes");
        else
            Console.WriteLine( "No");
    }
}
 
// This code is contributed by Ryuga

<?php
// PHP implementation of the approach
 
// Recursive function that returns true
// if the array can be divided into two
// sub-arrays satisfying the given condition
function helper(&$arr, $n, $start,
                    $lsum, $rsum)
{
 
    // If reached the end
    if ($start == $n)
        return $lsum == $rsum;
 
    // If divisible by 5 then
    // add to the left sum
    if ($arr[$start] % 5 == 0)
        $lsum += $arr[$start];
 
    // If divisible by 3 but not by 5
    // then add to the right sum
    else if ($arr[$start] % 3 == 0)
        $rsum += $arr[$start];
 
    // Else it can be added to any
    // of the sub-arrays
    else
 
        // Try adding in both the sub-arrays (one by one)
        // and check whether the condition satisfies
        return helper($arr, $n, $start + 1,
                      $lsum + $arr[$start], $rsum) ||
               helper($arr, $n, $start + 1,
                      $lsum, $rsum + $arr[$start]);
 
    // For cases when element is
    // multiple of 3 or 5.
    return helper($arr, $n, $start + 1,
                        $lsum, $rsum);
}
 
// Function to start the recursive calls
function splitArray($arr, $n)
{
    // Initially start, lsum and r
    // sum will all be 0
    return helper($arr, $n, 0, 0, 0);
}
 
// Driver code
$arr = array( 1, 4, 3 );
$n = count($arr);
 
if (splitArray($arr, $n))
    print("Yes");
else
    print("No");
 
// This code is contributed by mits
?>

<script>
 
//js implementation of the approach
 
// Recursive function that returns true if the array
// can be divided into two sub-arrays
// satisfying the given condition
function helper( arr, n, start, lsum, rsum)
{
    // If reached the end
    if (start == n)
        return lsum == rsum;
 
    // If divisible by 5 then add to the left sum
    if (arr[start] % 5 == 0)
        lsum += arr[start];
 
    // If divisible by 3 but not by 5
    // then add to the right sum
    else if (arr[start] % 3 == 0)
        rsum += arr[start];
 
    // Else it can be added to any of the sub-arrays
    else
 
        // Try adding in both the sub-arrays (one by one)
        // and check whether the condition satisfies
        return helper(arr, n, start + 1, lsum + arr[start], rsum)
           || helper(arr, n, start + 1, lsum, rsum + arr[start]);
 
    // For cases when element is multiple of 3 or 5.
    return helper(arr, n, start + 1, lsum, rsum);
}
 
// Function to start the recursive calls
function splitArray(arr, n)
{
    // Initially start, lsum and rsum will all be 0
    return helper(arr, n, 0, 0, 0);
}
 
// Driver code
let arr = [1, 4, 3 ];
let n =arr.length;
if (splitArray(arr, n))
    document.write( "Yes");
else
     document.write( "No");
 
</script>

Yes

Complejidad temporal: O(2 ^ N)
Espacio auxiliar: O(N)