Encuentre la suma de todas las sumas de subarreglos únicos para una array determinada.

Dada una array de elementos n-positivos. La suma de sub-arrays se define como la suma de todos los elementos de una sub-array en particular, la tarea es encontrar la suma de todas las sumas de sub-arrays únicas. 
Nota: La suma única de subarreglo significa que ningún otro subarreglo tendrá el mismo valor de suma. 

Ejemplos:

Entrada: arr[] = {3, 4, 5} 
Salida: 40 
Explicación: Todos los subconjuntos únicos posibles con su suma son como: 
(3), (4), (5), (3+4), (4 +5), (3+4+5). Aquí todos son únicos, por lo que se requiere suma = 40

Entrada: arr[] = {2, 4, 2} 
Salida: 12 
Explicación: Todos los subconjuntos únicos posibles con su suma son como: 
(2), (4), (2), (2+4), (4 +2), (2+4+2). Aquí solo (4) y (2+4+2) son únicos.

Método 1 (Clasificación basada) 
1- Calcular la suma acumulada de una array. 
2- Almacenar toda la suma de sub-arrays en vector. 
3- Ordenar el vector. 
4- Marcar todas las sumas de subarrays duplicadas a cero 
5- Calcular y devolver totalSum.

// C++ for finding sum of all unique
// subarray sum
#include <bits/stdc++.h>
using namespace std;
 
// function for finding grandSum
long long int findSubarraySum(int arr[], int n)
{
    int i, j;
 
    // calculate cumulative sum of array
    // cArray[0] will store sum of zero elements
    long long int cArray[n + 1] = { 0 };
    for (i = 0; i < n; i++)
        cArray[i + 1] = cArray[i] + arr[i];
 
    vector<long long int> subArrSum;
 
    // store all subarray sum in vector
    for (i = 1; i <= n; i++)
        for (j = i; j <= n; j++)
            subArrSum.push_back(cArray[j] -
                                cArray[i - 1]);
 
    // sort the vector
    sort(subArrSum.begin(), subArrSum.end());
 
    // mark all duplicate sub-array
    // sum to zero
    long long totalSum = 0;
    for (i = 0; i < subArrSum.size() - 1; i++)
    {
        if (subArrSum[i] == subArrSum[i + 1])
        {
            j = i + 1;
            while (subArrSum[j] == subArrSum[i] &&
                                   j < subArrSum.size())
            {
                subArrSum[j] = 0;
                j++;
            }
            subArrSum[i] = 0;
        }
    }
 
    // calculate total sum
    for (i = 0; i < subArrSum.size(); i++)
        totalSum += subArrSum[i];
 
    // return totalSum
    return totalSum;
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 2, 3, 1, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSubarraySum(arr, n);
    return 0;
}

// Java for finding sum of all unique
// subarray sum
import java.util.*;
 
class GFG{
 
// Function for finding grandSum
static int findSubarraySum(int arr[], int n)
{
    int i, j;
 
    // Calculate cumulative sum of array
    // cArray[0] will store sum of zero elements
    int cArray[] = new int[n + 1];
    for(i = 0; i < n; i++)
        cArray[i + 1] = cArray[i] + arr[i];
 
    Vector<Integer> subArrSum = new Vector<Integer>();
 
    // Store all subarray sum in vector
    for(i = 1; i <= n; i++)
        for(j = i; j <= n; j++)
            subArrSum.add(cArray[j] -
                          cArray[i - 1]);
 
    // Sort the vector
    Collections.sort(subArrSum);
 
    // Mark all duplicate sub-array
    // sum to zero
    int totalSum = 0;
    for(i = 0; i < subArrSum.size() - 1; i++)
    {
        if (subArrSum.get(i) ==
            subArrSum.get(i + 1))
        {
            j = i + 1;
            while (subArrSum.get(j) ==
                   subArrSum.get(i) &&
               j < subArrSum.size())
            {
                subArrSum.set(j, 0);
                j++;
            }
            subArrSum.set(i, 0);
        }
    }
 
    // Calculate total sum
    for(i = 0; i < subArrSum.size(); i++)
        totalSum += subArrSum.get(i);
 
    // Return totalSum
    return totalSum;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 3, 2, 3, 1, 4 };
    int n = arr.length;
     
    System.out.print(findSubarraySum(arr, n));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 for finding sum of all
# unique subarray sum
 
# function for finding grandSum
def findSubarraySum(arr, n):
     
    # calculate cumulative sum of array
    # cArray[0] will store sum of zero elements
    cArray = [0 for i in range(n + 1)]
    for i in range(0, n, 1):
        cArray[i + 1] = cArray[i] + arr[i]
 
    subArrSum = []
 
    # store all subarray sum in vector
    for i in range(1, n + 1, 1):
        for j in range(i, n + 1, 1):
            subArrSum.append(cArray[j] -
                             cArray[i - 1])
 
    # sort the vector
    subArrSum.sort(reverse = False)
 
    # mark all duplicate sub-array
    # sum to zero
    totalSum = 0
    for i in range(0, len(subArrSum) - 1, 1):
        if (subArrSum[i] == subArrSum[i + 1]):
            j = i + 1
            while (subArrSum[j] == subArrSum[i] and
                           j < len(subArrSum)):
                subArrSum[j] = 0
                j += 1
            subArrSum[i] = 0
 
    # calculate total sum
    for i in range(0, len(subArrSum), 1):
        totalSum += subArrSum[i]
 
    # return totalSum
    return totalSum
 
# Drivers code
if __name__ == '__main__':
    arr = [3, 2, 3, 1, 4]
    n = len(arr)
    print(findSubarraySum(arr, n))
     
# This code is contributed by
# Sahil_Shelangia

// C# for finding sum of all unique
// subarray sum
using System;
using System.Collections.Generic;
class GFG{
 
// Function for finding grandSum
static int findSubarraySum(int []arr,
                           int n)
{
  int i, j;
 
  // Calculate cumulative sum
  // of array cArray[0] will
  // store sum of zero elements
  int []cArray = new int[n + 1];
   
  for(i = 0; i < n; i++)
    cArray[i + 1] = cArray[i] + arr[i];
 
  List<int> subArrSum = new List<int>();
 
  // Store all subarray sum in vector
  for(i = 1; i <= n; i++)
    for(j = i; j <= n; j++)
      subArrSum.Add(cArray[j] -
                    cArray[i - 1]);
 
  // Sort the vector
  subArrSum.Sort();
 
  // Mark all duplicate
  // sub-array sum to zero
  int totalSum = 0;
  for(i = 0; i < subArrSum.Count - 1; i++)
  {
    if (subArrSum[i] ==
        subArrSum[i + 1])
    {
      j = i + 1;
      while (subArrSum[j] ==
             subArrSum[i] &&
             j < subArrSum.Count)
      {
        subArrSum[j] = 0;
        j++;
      }
      subArrSum[i] = 0;
    }
  }
 
  // Calculate total sum
  for(i = 0; i < subArrSum.Count; i++)
    totalSum += subArrSum[i];
 
  // Return totalSum
  return totalSum;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = {3, 2, 3, 1, 4};
    int n = arr.Length;   
    Console.Write(findSubarraySum(arr, n));
}
}
 
// This code is contributed by Rajput-Ji

<script>
      // JavaScript for finding sum of all unique
      // subarray sum
      // Function for finding grandSum
      function findSubarraySum(arr, n) {
        var i, j;
 
        // Calculate cumulative sum
        // of array cArray[0] will
        // store sum of zero elements
        var cArray = new Array(n + 1).fill(0);
 
        for (i = 0; i < n; i++)
        cArray[i + 1] = cArray[i] + arr[i];
 
        var subArrSum = [];
 
        // Store all subarray sum in vector
        for (i = 1; i <= n; i++)
          for (j = i; j <= n; j++) subArrSum.push(cArray[j] - cArray[i - 1]);
 
        // Sort the vector
        subArrSum.sort();
 
        // Mark all duplicate
        // sub-array sum to zero
        var totalSum = 0;
        for (i = 0; i < subArrSum.length - 1; i++) {
          if (subArrSum[i] == subArrSum[i + 1]) {
            j = i + 1;
            while (subArrSum[j] == subArrSum[i] && j < subArrSum.length) {
              subArrSum[j] = 0;
              j++;
            }
            subArrSum[i] = 0;
          }
        }
 
        // Calculate total sum
        for (i = 0; i < subArrSum.length; i++) totalSum += subArrSum[i];
 
        // Return totalSum
        return totalSum;
      }
 
      // Driver Code
      var arr = [3, 2, 3, 1, 4];
      var n = arr.length;
      document.write(findSubarraySum(arr, n));
       
      // This code is contributed by rdtank.
    </script>

41

Complejidad de tiempo: O(N^2 + N * logN)

Espacio Auxiliar: O(N)

Método 2 (basado en hash) La idea es hacer una tabla hash vacía. Generamos todos los subarreglos. Para cada subarreglo, calculamos su suma y el recuento de incrementos de la suma en la tabla hash. Finalmente, sumamos todas aquellas sumas cuya cuenta es 1.

// C++ for finding sum of all unique subarray sum
#include <bits/stdc++.h>
using namespace std;
 
// function for finding grandSum
long long int findSubarraySum(int arr[], int n)
{
    int res = 0;
 
    // Go through all subarrays, compute sums
    // and count occurrences of sums.
    unordered_map<int, int> m;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            m[sum]++;
        }
    }
 
    // Print all those sums that appear
    // once.
    for (auto x : m)
        if (x.second == 1)
            res += x.first;
 
    return res;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 2, 3, 1, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSubarraySum(arr, n);
    return 0;
}

// Java for finding sum of all
// unique subarray sum
import java.util.*;
 
class GFG
{
 
// function for finding grandSum
static int findSubarraySum(int []arr, int n)
{
    int res = 0;
 
    // Go through all subarrays, compute sums
    // and count occurrences of sums.
    HashMap<Integer,
            Integer> m = new HashMap<Integer,
                                     Integer>();
    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[j];
            if (m.containsKey(sum))
            {
                m.put(sum, m.get(sum) + 1);
            }
            else
            {
                m.put(sum, 1);
            }
        }
    }
 
    // Print all those sums that appear
    // once.
    for (Map.Entry<Integer,
                   Integer> x : m.entrySet())
        if (x.getValue() == 1)
            res += x.getKey();
 
    return res;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 2, 3, 1, 4 };
    int n = arr.length;
    System.out.println(findSubarraySum(arr, n));
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 for finding sum of all
# unique subarray sum
 
# function for finding grandSum
def findSubarraySum(arr, n):
 
    res = 0
 
    # Go through all subarrays, compute sums
    # and count occurrences of sums.
    m = dict()
    for i in range(n):
        Sum = 0
        for j in range(i, n):
            Sum += arr[j]
            m[Sum] = m.get(Sum, 0) + 1
         
    # Print all those Sums that appear
    # once.
    for x in m:
        if m[x] == 1:
            res += x
 
    return res
 
# Driver code
arr = [3, 2, 3, 1, 4]
n = len(arr)
print(findSubarraySum(arr, n))
 
# This code is contributed by mohit kumar

// C# for finding sum of all
// unique subarray sum
using System;
using System.Collections.Generic;
     
class GFG
{
 
// function for finding grandSum
static int findSubarraySum(int []arr, int n)
{
    int res = 0;
 
    // Go through all subarrays, compute sums
    // and count occurrences of sums.
    Dictionary<int,
               int> m = new Dictionary<int,
                                       int>();
    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[j];
            if (m.ContainsKey(sum))
            {
                m[sum] = m[sum] + 1;
            }
            else
            {
                m.Add(sum, 1);
            }
        }
    }
 
    // Print all those sums that appear
    // once.
    foreach(KeyValuePair<int, int> x in m)
        if (x.Value == 1)
            res += x.Key;
 
    return res;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 3, 2, 3, 1, 4 };
    int n = arr.Length;
    Console.WriteLine(findSubarraySum(arr, n));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript for finding sum of all
// unique subarray sum
 
// Function for finding grandSum
function findSubarraySum(arr, n)
{
    let res = 0;
     
    // Go through all subarrays, compute sums
    // and count occurrences of sums.
    let m = new Map();
    for(let i = 0; i < n; i++)
    {
        let sum = 0;
        for(let j = i; j < n; j++)
        {
            sum += arr[j];
            if (m.has(sum))
            {
                m.set(sum, m.get(sum) + 1);
            }
            else
            {
                m.set(sum, 1);
            }
        }
    }
     
    // Print all those sums that appear
    // once.
    for(let x of m)
        if (x[1] == 1)
            res += x[0];
     
    return res;
}
 
// Driver code
let arr = [ 3, 2, 3, 1, 4 ];
let n = arr.length;
 
document.write(findSubarraySum(arr, n));
 
// This code is contributed by gfgking
 
</script>

41

Complejidad del tiempo: O(N^2)

Espacio Auxiliar: O(N)