Número de veces que una array se puede dividir repetidamente en dos subarreglos con la misma suma

Dada una array arr[] de tamaño N , la tarea es encontrar el número de veces que la array se puede dividir repetidamente en dos subarreglos de modo que la suma de los elementos de ambos subarreglos sea la misma .

Ejemplos: 

Entrada: arr[] = { 2, 2, 2, 2 } 
Salida: 3 
Explicación: 
1. Haga la primera partición después del índice 1. Las arrays restantes son {2, 2} en el lado derecho y en el lado izquierdo. 
2. Considere el subarreglo izquierdo {2, 2}. Haga una partición después del índice 0 de este subarreglo izquierdo. 
Ahora se forman dos subarreglos similares con un elemento cada uno, es decir, {2}, que no se pueden subdividir. 
3. Considere el subarreglo derecho {2, 2}. Haga una partición después del índice 0 de este subarreglo izquierdo. 
Ahora se forman dos subarreglos similares con un elemento cada uno, es decir, {2}, que no se pueden subdividir. 
Por lo tanto, la salida es 3 ya que la array se particionó 3 veces.

Entrada: arr[] = {12, 3, 3, 0, 3, 3} 
Salida: 4 
Explicación: 
1. La primera partición está después del índice 0. La array restante es arr[] = {3, 3, 0, 3, 3}. 
2. La segunda partición está después del índice 1. La array restante es {3, 3} y {0, 3, 3}. 
3. La tercera partición está después del índice 0 en la array {3, 3}. 
4. La cuarta partición está después de 1 en la array {0, 3, 3} 
La array restante es {0, 3} y {3} que no se pueden subdividir. 
Por lo tanto, la salida es 4. 

Enfoque: La idea es usar Recursión . A continuación se muestran los pasos:  

1. Encuentre la suma de prefijos de la array dada arr[] y guárdela en una array pref[] .
2. Iterar desde la posición inicial hasta la posición final.
3. Para cada posible índice de partición (digamos K ), si prefix_sum[K] – prefix_sum[start-1] = prefix_sum[end] – prefix_sum[k] , entonces la partición es válida.
4. Si una partición es válida en el paso anterior, proceda con los subconjuntos izquierdo y derecho por separado y determine si estos dos subconjuntos forman una partición válida o no.
5. Repita los pasos 3 y 4 para la partición izquierda y derecha hasta que no sea posible realizar más particiones.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Recursion Function to calculate the
// possible splitting
int splitArray(int start, int end,
               int* arr,
               int* prefix_sum)
{
    // If there are less than
    // two elements, we cannot
    // partition the sub-array.
    if (start >= end)
        return 0;
 
    // Iterate from the start
    // to end-1.
    for (int k = start; k < end; ++k) {
 
        if ((prefix_sum[k] - prefix_sum[start - 1])
            == (prefix_sum[end] - prefix_sum[k])) {
 
            // Recursive call to the left
            // and the right sub-array.
            return 1 + splitArray(start,
                                  k,
                                  arr,
                                  prefix_sum)
                   + splitArray(k + 1,
                                end,
                                arr,
                                prefix_sum);
        }
    }
 
    // If there is no such partition,
    // then return 0
    return 0;
}
 
// Function to find the total splitting
void solve(int arr[], int n)
{
 
    // Prefix array to store
    // the prefix-sum using
    // 1 based indexing
    int prefix_sum[n + 1];
 
    prefix_sum[0] = 0;
 
    // Store the prefix-sum
    for (int i = 1; i <= n; ++i) {
        prefix_sum[i] = prefix_sum[i - 1]
                        + arr[i - 1];
    }
 
    // Function Call to count the
    // number of splitting
    cout << splitArray(1, n,
                       arr,
                       prefix_sum);
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 12, 3, 3, 0, 3, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    solve(arr, N);
    return 0;
}

// Java program for the above approach
class GFG{
 
// Recursion Function to calculate the
// possible splitting
static int splitArray(int start, int end,
                      int[] arr,
                      int[] prefix_sum)
{
    // If there are less than
    // two elements, we cannot
    // partition the sub-array.
    if (start >= end)
        return 0;
 
    // Iterate from the start
    // to end-1.
    for (int k = start; k < end; ++k)
    {
        if ((prefix_sum[k] - prefix_sum[start - 1]) ==
            (prefix_sum[end] - prefix_sum[k]))
        {
 
            // Recursive call to the left
            // and the right sub-array.
            return 1 + splitArray(start, k, arr, prefix_sum) +
                       splitArray(k + 1, end, arr, prefix_sum);
        }
    }
 
    // If there is no such partition,
    // then return 0
    return 0;
}
 
// Function to find the total splitting
static void solve(int arr[], int n)
{
 
    // Prefix array to store
    // the prefix-sum using
    // 1 based indexing
    int []prefix_sum = new int[n + 1];
 
    prefix_sum[0] = 0;
 
    // Store the prefix-sum
    for (int i = 1; i <= n; ++i)
    {
        prefix_sum[i] = prefix_sum[i - 1] +
                               arr[i - 1];
    }
 
    // Function Call to count the
    // number of splitting
    System.out.print(splitArray(1, n, arr,
                                prefix_sum));
}
 
// Driver Code
public static void main(String[] args)
{
    // Given array
    int arr[] = { 12, 3, 3, 0, 3, 3 };
    int N = arr.length;
 
    // Function call
    solve(arr, N);
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Recursion Function to calculate the
# possible splitting
def splitArray(start, end, arr, prefix_sum):
     
    # If there are less than
    # two elements, we cannot
    # partition the sub-array.
    if (start >= end):
        return 0
 
    # Iterate from the start
    # to end-1.
    for k in range(start, end):
        if ((prefix_sum[k] - prefix_sum[start - 1]) ==
            (prefix_sum[end] - prefix_sum[k])) :
 
            # Recursive call to the left
            # and the right sub-array.
            return (1 + splitArray(start, k, arr,
                                   prefix_sum) +
                        splitArray(k + 1, end, arr,
                                   prefix_sum))
         
    # If there is no such partition,
    # then return 0
    return 0
 
# Function to find the total splitting
def solve(arr, n):
 
    # Prefix array to store
    # the prefix-sum using
    # 1 based indexing
    prefix_sum = [0] * (n + 1)
 
    prefix_sum[0] = 0
 
    # Store the prefix-sum
    for i in range(1, n + 1):
        prefix_sum[i] = (prefix_sum[i - 1] +
                                arr[i - 1])
     
    # Function Call to count the
    # number of splitting
    print(splitArray(1, n, arr, prefix_sum))
 
# Driver Code
 
# Given array
arr = [ 12, 3, 3, 0, 3, 3 ]
N = len(arr)
 
# Function call
solve(arr, N)
 
# This code is contributed by sanjoy_62

// C# program for the above approach
using System;
 
class GFG{
 
// Recursion Function to calculate the
// possible splitting
static int splitArray(int start, int end,
                      int[] arr,
                      int[] prefix_sum)
{
     
    // If there are less than
    // two elements, we cannot
    // partition the sub-array.
    if (start >= end)
        return 0;
 
    // Iterate from the start
    // to end-1.
    for(int k = start; k < end; ++k)
    {
       if ((prefix_sum[k] -
            prefix_sum[start - 1]) ==
           (prefix_sum[end] -
            prefix_sum[k]))
       {
            
           // Recursive call to the left
           // and the right sub-array.
           return 1 + splitArray(start, k, arr,
                                 prefix_sum) +
                      splitArray(k + 1, end, arr,
                                 prefix_sum);
       }
    }
     
    // If there is no such partition,
    // then return 0
    return 0;
}
 
// Function to find the total splitting
static void solve(int []arr, int n)
{
     
    // Prefix array to store
    // the prefix-sum using
    // 1 based indexing
    int []prefix_sum = new int[n + 1];
 
    prefix_sum[0] = 0;
 
    // Store the prefix-sum
    for(int i = 1; i <= n; ++i)
    {
       prefix_sum[i] = prefix_sum[i - 1] +
                              arr[i - 1];
    }
 
    // Function Call to count the
    // number of splitting
    Console.Write(splitArray(1, n, arr,
                             prefix_sum));
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array
    int []arr = { 12, 3, 3, 0, 3, 3 };
    int N = arr.Length;
 
    // Function call
    solve(arr, N);
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// JavaScript program to implement
// the above approach
 
// Recursion Function to calculate the
// possible splitting
function splitArray(start, end, arr, prefix_sum)
{
    // If there are less than
    // two elements, we cannot
    // partition the sub-array.
    if (start >= end)
        return 0;
   
    // Iterate from the start
    // to end-1.
    for (let k = start; k < end; ++k)
    {
        if ((prefix_sum[k] - prefix_sum[start - 1]) ==
            (prefix_sum[end] - prefix_sum[k]))
        {
   
            // Recursive call to the left
            // and the right sub-array.
            return 1 + splitArray(start, k, arr, prefix_sum) +
                       splitArray(k + 1, end, arr, prefix_sum);
        }
    }
   
    // If there is no such partition,
    // then return 0
    return 0;
}
   
// Function to find the total splitting
function solve(arr, n)
{
   
    // Prefix array to store
    // the prefix-sum using
    // 1 based indexing
    let prefix_sum = Array.from({length: n+1}, (_, i) => 0);
   
    prefix_sum[0] = 0;
   
    // Store the prefix-sum
    for (let i = 1; i <= n; ++i)
    {
        prefix_sum[i] = prefix_sum[i - 1] +
                               arr[i - 1];
    }
   
    // Function Call to count the
    // number of splitting
   document.write(splitArray(1, n, arr,
                                prefix_sum));
}
 
// Driver code
 
    // Given array
    let arr = [ 12, 3, 3, 0, 3, 3 ];
    let N = arr.length;
   
    // Function call
    solve(arr, N);
 
// This code is contributed by code_hunt.
</script>

4

Tiempo Complejidad: O(N ² )  
Espacio Auxiliar: O(N)