Encuentre las sumas para las cuales una array se puede dividir en sub-arrays de igual suma

Dada una array de enteros arr[] , la tarea es encontrar todos los valores para sum de modo que para un valor sum[i] la array se pueda dividir en sub-arrays de sum igual a sum[i] . Si la array no se puede dividir en sub-arrays de igual suma, imprima -1 .
Ejemplos: 
 

Entrada: arr[] = {2, 2, 2, 1, 1, 2, 2} 
Salida: 2 4 6 
La array se puede dividir en sub-arrays de suma 2, 4 y 6. 
{2}, {2} , {2}, {1, 1}, {2} y {2} 
{2, 2}, {2, 1, 1} y {2, 2} 
{2, 2, 2} y {1, 1, 2, 2}
Entrada: arr[] = {1, 1, 2} 
Salida: 2 
La array se puede dividir en sub-arrays de suma 2. 
{1, 1} y {2} 
 

Enfoque: Cree una array de suma de prefijos P[] donde P[i] almacena la suma de elementos desde el índice 0 hasta i . Los divisores de la suma total S solo pueden ser la posible suma de subarreglo. Entonces, para cada divisor, si todos los múltiplos del divisor hasta la suma total S están presentes en la array P[] , entonces esa sería una posible suma de sub-arrays. Marque todos los elementos de P[] en un mapa como 1 para que la búsqueda sea fácil. Todos los divisores se pueden verificar en tiempo sqrt (S) .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find the sums for which an array
// can be divided into subarrays of equal sum.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sums for which an array
// can be divided into subarrays of equal sum
void getSum(int a[], int n)
{
    int P[n];
 
    // Creating prefix sum array
    P[0] = a[0];
    for (int i = 1; i < n; i++)
        P[i] = a[i] + P[i - 1];
 
    // Total Sum
    int S = P[n - 1];
 
    // Initializing a Map for look-up
    map<int, int> hash;
 
    // Setting all the present sum as 1
    for (int i = 0; i < n; i++)
        hash[P[i]] = 1;
 
    // Set to store the subarray sum
    set<int> res;
 
    // Check the divisors of S
    for (int i = 1; i * i <= S; i++) {
        if (S % i == 0) {
            bool pres = true;
 
            int div1 = i, div2 = S / i;
 
            // Check if all multiples of div1 present or not
            for (int j = div1; j <= S; j += div1) {
                if (hash[j] != 1) {
                    pres = false;
                    break;
                }
            }
 
            // If all multiples are present
            if (pres and div1 != S)
                res.insert(div1);
 
            pres = true;
 
            // Check if all multiples of div2 present or not
            for (int j = S / i; j <= S; j += S / i) {
                if (hash[j] != 1) {
                    pres = false;
                    break;
                }
            }
 
            // If all multiples are present
            if (pres and div2 != S)
                res.insert(div2);
        }
    }
 
    // If array cannot be divided into
    // sub-arrays of equal sum
    if(res.size() == 0) {
        cout << "-1";
        return;
    }
 
    // Printing the results
    for (auto i : res)
        cout << i << " ";
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 1, 1, 1, 2, 1, 3 };
 
    int n = sizeof(a) / sizeof(a[0]);
 
    getSum(a, n);
 
    return 0;
}

// Java program to find the sums for which an array
// can be divided into subarrays of equal sum.
import java.util.HashMap;
import java.util.HashSet;
 
class GFG {
 
    // Function to find the sums for which an array
    // can be divided into subarrays of equal sum
    public static void getSum(int[] a, int n)
    {
        int[] P = new int[n];
 
        // Creating prefix sum array
        P[0] = a[0];
        for (int i = 1; i < n; i++)
            P[i] = a[i] + P[i - 1];
 
        // Total Sum
        int S = P[n - 1];
 
        HashMap<Integer, Integer> hash = new HashMap<>();
 
        // Setting all the present sum as 1
        for (int i = 0; i < n; i++)
            hash.put(P[i], 1);
 
        // Set to store the subarray sum
        HashSet<Integer> res = new HashSet<>();
 
        // Check the divisors of S
        for (int i = 1; i * i <= S; i++)
        {
            if (S % i == 0)
            {
                boolean pres = true;
 
                int div1 = i, div2 = S / i;
 
                // Check if all multiples of div1 present or not
                for (int j = div1; j <= S; j += div1)
                {
                    if (hash.get(j) == null || hash.get(j) != 1)
                    {
                        pres = false;
                        break;
                    }
                }
 
                // If all multiples are present
                if (pres && div1 != S)
                    res.add(div1);
 
                pres = true;
 
                // Check if all multiples of div2 present or not
                for (int j = S / i; j <= S; j += S / i)
                {
                    if (hash.get(j) == null || hash.get(j) != 1)
                    {
                        pres = false;
                        break;
                    }
                }
 
                // If all multiples are present
                if (pres && div2 != S)
                    res.add(div2);
            }
        }
 
        // If array cannot be divided into
        // sub-arrays of equal sum
        if (res.size() == 0)
        {
            System.out.println("-1");
            return;
        }
 
        // Printing the results
        for (int i : res)
            System.out.print(i + " ");
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] a = { 1, 2, 1, 1, 1, 2, 1, 3 };
        int n = a.length;
        getSum(a, n);
    }
}
 
// This code is contributed by
// sanjeev2552

# Python3 program to find the sums for
# which an array can be divided into
# subarrays of equal sum.
 
# from math lib import sqrt function
from math import sqrt
 
# Function to find the sums for which
# an array can be divided into subarrays
# of equal sum
def getSum(a, n) :
     
    P = [0] * n
 
    # Creating prefix sum array
    P[0] = a[0]
    for i in range(1, n) :
        P[i] = a[i] + P[i - 1]
 
    # Total Sum
    S = P[n - 1]
 
    # Initializing a Map for look-up
    hash = {}
 
    # Setting all the present sum as 1
    for i in range(n) :
        hash[P[i]] = 1
 
    # Set to store the subarray sum
    res = set()
 
    # Check the divisors of S
    for i in range(1, int(sqrt(S)) + 1) :
        if (S % i == 0) :
            pres = True;
 
            div1 = i
            div2 = S // i
 
            # Check if all multiples of
            # div1 present or not
            for j in range(div1 , S + 1, div1) :
                 
                if j not in hash.keys() :
                    pres = False
                    break
 
            # If all multiples are present
            if (pres and div1 != S) :
                res.add(div1)
 
            pres = True
 
            # Check if all multiples of div2
            # present or not
            for j in range(S // i , S + 1 , S // i) :
                if j not in hash.keys():
                    pres = False;
                    break
 
            # If all multiples are present
            if (pres and div2 != S) :
                res.add(div2)
 
    # If array cannot be divided into
    # sub-arrays of equal sum
    if(len(res) == 0) :
        print("-1")
        return
 
    # Printing the results
    for i in res :
        print(i, end = " ")
 
# Driver code
if __name__ == "__main__" :
 
    a = [ 1, 2, 1, 1, 1, 2, 1, 3 ]
 
    n = len(a)
 
    getSum(a, n)
 
# This code is contributed by Ryuga

// C# program to find the sums for which
// an array can be divided into subarrays
// of equal sum.
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to find the sums for which
// an array can be divided into subarrays
// of equal sum
public static void getSum(int[] a, int n)
{
    int[] P = new int[n];
 
    // Creating prefix sum array
    P[0] = a[0];
    for (int i = 1; i < n; i++)
        P[i] = a[i] + P[i - 1];
 
    // Total Sum
    int S = P[n - 1];
 
    Dictionary<int,
               int> hash = new Dictionary<int,
                                          int>();
 
    // Setting all the present sum as 1
    for (int i = 0; i < n; i++)
        if(!hash.ContainsKey(P[i]))
            hash.Add(P[i], 1);
 
    // Set to store the subarray sum
    HashSet<int> res = new HashSet<int>();
 
    // Check the divisors of S
    for (int i = 1; i * i <= S; i++)
    {
        if (S % i == 0)
        {
            Boolean pres = true;
 
            int div1 = i, div2 = S / i;
 
            // Check if all multiples of
            // div1 present or not
            for (int j = div1; j <= S; j += div1)
            {
                if (!hash.ContainsKey(j) ||
                     hash[j] != 1)
                {
                    pres = false;
                    break;
                }
            }
 
            // If all multiples are present
            if (pres && div1 != S)
                res.Add(div1);
 
            pres = true;
 
            // Check if all multiples of
            // div2 present or not
            for (int j = S / i;
                     j <= S; j += S / i)
            {
                if (hash[j] == 0 ||
                    hash[j] != 1)
                {
                    pres = false;
                    break;
                }
            }
 
            // If all multiples are present
            if (pres && div2 != S)
                res.Add(div2);
        }
    }
 
    // If array cannot be divided into
    // sub-arrays of equal sum
    if (res.Count == 0)
    {
        Console.WriteLine("-1");
        return;
    }
 
    // Printing the results
    foreach (int i in res)
        Console.Write(i + " ");
}
 
// Driver code
public static void Main(String[] args)
{
    int[] a = { 1, 2, 1, 1, 1, 2, 1, 3 };
    int n = a.Length;
    getSum(a, n);
}
}
 
// This code is contributed by PrinciRaj1992

<script>
// Javascript program to find the sums for which an array
// can be divided into subarrays of equal sum.
 
 
// Function to find the sums for which an array
// can be divided into subarrays of equal sum
function getSum(a, n) {
    let P = new Array(n);
 
    // Creating prefix sum array
    P[0] = a[0];
    for (let i = 1; i < n; i++)
        P[i] = a[i] + P[i - 1];
 
    // Total Sum
    let S = P[n - 1];
 
    // Initializing a Map for look-up
    let hash = new Map();
 
    // Setting all the present sum as 1
    for (let i = 0; i < n; i++)
        hash.set(P[i], 1);
 
    // Set to store the subarray sum
    let res = new Set();
 
    // Check the divisors of S
    for (let i = 1; i * i <= S; i++) {
        if (S % i == 0) {
            let pres = true;
 
            let div1 = i, div2 = Math.floor(S / i);
 
            // Check if all multiples of div1 present or not
            for (let j = div1; j <= S; j += div1) {
                if (hash.get(j) != 1) {
                    pres = false;
                    break;
                }
            }
 
            // If all multiples are present
            if (pres && div1 != S)
                res.add(div1);
 
            pres = true;
 
            // Check if all multiples of div2 present or not
            for (let j = Math.floor(S / i); j <= S; j += Math.floor(S / i)) {
                if (hash.get(j) != 1) {
                    pres = false;
                    break;
                }
            }
 
            // If all multiples are present
            if (pres && div2 != S)
                res.add(div2);
        }
    }
 
    // If array cannot be divided into
    // sub-arrays of equal sum
    if (res.size == 0) {
        document.write("-1");
        return;
    }
 
    res = [...res].sort((a, b) => a - b)
 
    // Printing the results
    for (let i of res)
        document.write(i + " ");
}
 
// Driver code
let a = [1, 2, 1, 1, 1, 2, 1, 3];
let n = a.length;
getSum(a, n);
 
// This code is contributed by gfgking.
</script>

3 4 6

Complejidad de tiempo: O(nlogn), para verificar divisores y múltiplos
Espacio auxiliar: O(n), ya que se usa un espacio adicional de tamaño n