Número de formas de dividir una array en K sub-arrays de igual suma

Dado un entero K y una array arr[] de N enteros, la tarea es encontrar el número de formas de dividir la array en K sub-arrays de igual suma de longitudes distintas de cero.

Ejemplos:  

Entrada: arr[] = {0, 0, 0, 0}, K = 3 
Salida: 3 
Todas las formas posibles son: 
{{0}, {0}, {0, 0}} 
{{0}, {0, 0}, {0}} 
{{0, 0}, {0}, {0}}
Entrada: arr[] = {1, -1, 1, -1}, K = 2 
Salida: 1  

Enfoque: Este problema se puede resolver mediante programación dinámica . El siguiente será nuestro algoritmo: 

1. Encuentra la suma de todos los elementos de la array y guárdala en una variable SUM . 
   Antes de ir al paso 2, intentemos comprender los estados del DP. 
   Para eso, visualiza poner barras para dividir la array en K partes iguales. Entonces, tenemos que poner K – 1 barra en total. 
   Así, nuestros estados de dp contendrán 2 términos. 
   • i – índice del elemento en el que nos encontramos actualmente.
   • ck – número de compases que ya hemos insertado + 1.
2. Llame a una función recursiva con i = 0 y ck = 1 y la relación de recurrencia será:

Caso 1: suma hasta el índice i es igual a ((SUMA)/k)* ck 
dp[i][ck] = dp[i+1][ck] + dp[i+1][ck+1] 
Caso 2: suma hasta el índice no i es igual a ((SUMA)/k)* ck 
dp[i][ck] = dp[i+1][ck] 
 

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

// C++ implementation of the approach
#include <bits/stdc++.h>
#define max_size 20
#define max_k 20
using namespace std;
 
// Array to store the states of DP
int dp[max_size][max_k];
 
// Array to check if a
// state has been solved before
bool v[max_size][max_k];
 
// To store the sum of
// the array elements
int sum = 0;
 
// Function to find the sum of
// all the array elements
void findSum(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        sum += arr[i];
}
 
// Function to return the number of ways
int cntWays(int arr[], int i, int ck,
            int k, int n, int curr_sum)
{
    // If sum is not divisible by k
    // answer will be zero
    if (sum % k != 0)
        return 0;
    if (i != n and ck == k + 1)
        return 0;
 
    // Base case
    if (i == n) {
        if (ck == k + 1)
            return 1;
        else
            return 0;
    }
 
    // To check if a state
    // has been solved before
    if (v[i][ck])
        return dp[i][ck];
 
    // Sum of all the numbers from the beginning
    // of the array
    curr_sum += arr[i];
 
    // Setting the current state as solved
    v[i][ck] = 1;
 
    // Recurrence relation
    dp[i][ck] = cntWays(arr, i + 1, ck, k, n, curr_sum);
    if (curr_sum == (sum / k) * ck)
        dp[i][ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum);
 
    // Returning solved state
    return dp[i][ck];
}
 
// Driver code
int main()
{
    int arr[] = { 1, -1, 1, -1, 1, -1 };
    int n = sizeof(arr) / sizeof(int);
    int k = 2;
 
    // Function call to find the
    // sum of the array elements
    findSum(arr, n);
 
    // Print the number of ways
    cout << cntWays(arr, 0, 1, k, n, 0);
}

// Java implementation of the approach
class GFG
{
     
static int max_size= 20;
static int max_k =20;
 
// Array to store the states of DP
static int [][]dp = new int[max_size][max_k];
 
// Array to check if a
// state has been solved before
static boolean [][]v = new boolean[max_size][max_k];
 
// To store the sum of
// the array elements
static int sum = 0;
 
// Function to find the sum of
// all the array elements
static void findSum(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        sum += arr[i];
}
 
// Function to return the number of ways
static int cntWays(int arr[], int i, int ck,
            int k, int n, int curr_sum)
{
    // If sum is not divisible by k
    // answer will be zero
    if (sum % k != 0)
        return 0;
    if (i != n && ck == k + 1)
        return 0;
 
    // Base case
    if (i == n)
    {
        if (ck == k + 1)
            return 1;
        else
            return 0;
    }
 
    // To check if a state
    // has been solved before
    if (v[i][ck])
        return dp[i][ck];
 
    // Sum of all the numbers from the beginning
    // of the array
    curr_sum += arr[i];
 
    // Setting the current state as solved
    v[i][ck] = true;
 
    // Recurrence relation
    dp[i][ck] = cntWays(arr, i + 1, ck, k, n, curr_sum);
    if (curr_sum == (sum / k) * ck)
        dp[i][ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum);
 
    // Returning solved state
    return dp[i][ck];
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, -1, 1, -1, 1, -1 };
    int n = arr.length;
    int k = 2;
 
    // Function call to find the
    // sum of the array elements
    findSum(arr, n);
 
    // Print the number of ways
    System.out.println(cntWays(arr, 0, 1, k, n, 0));
}
}
 
// This code is contributed by Princi Singh

# Python3 implementation of the approach
import numpy as np
 
max_size = 20
max_k = 20
 
 
# Array to store the states of DP
dp = np.zeros((max_size,max_k));
 
# Array to check if a
# state has been solved before
v = np.zeros((max_size,max_k));
 
# To store the sum of
# the array elements
sum = 0;
 
# Function to find the sum of
# all the array elements
def findSum(arr, n) :
    global sum
    for i in range(n) :
        sum += arr[i];
 
 
# Function to return the number of ways
def cntWays(arr, i, ck, k, n,  curr_sum) :
 
    # If sum is not divisible by k
    # answer will be zero
    if (sum % k != 0) :
        return 0;
    if (i != n and ck == k + 1) :
        return 0;
 
    # Base case
    if (i == n) :
        if (ck == k + 1) :
            return 1;
        else :
            return 0;
 
    # To check if a state
    # has been solved before
    if (v[i][ck]) :
        return dp[i][ck];
 
    # Sum of all the numbers from the beginning
    # of the array
    curr_sum += arr[i];
 
    # Setting the current state as solved
    v[i][ck] = 1;
 
    # Recurrence relation
    dp[i][ck] = cntWays(arr, i + 1, ck, k, n, curr_sum);
    if (curr_sum == (sum / k) * ck)  :
        dp[i][ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum);
 
    # Returning solved state
    return dp[i][ck];
  
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 1, -1, 1, -1, 1, -1 ];
    n = len(arr);
    k = 2;
 
    # Function call to find the
    # sum of the array elements
    findSum(arr, n);
 
    # Print the number of ways
    print(cntWays(arr, 0, 1, k, n, 0));
 
    # This code is contributed by AnkitRai01

// C# implementation of the approach
using System;    
     
class GFG
{
     
static int max_size= 20;
static int max_k =20;
 
// Array to store the states of DP
static int [,]dp = new int[max_size, max_k];
 
// Array to check if a
// state has been solved before
static Boolean [,]v = new Boolean[max_size, max_k];
 
// To store the sum of
// the array elements
static int sum = 0;
 
// Function to find the sum of
// all the array elements
static void findSum(int []arr, int n)
{
    for (int i = 0; i < n; i++)
        sum += arr[i];
}
 
// Function to return the number of ways
static int cntWays(int []arr, int i, int ck,
            int k, int n, int curr_sum)
{
    // If sum is not divisible by k
    // answer will be zero
    if (sum % k != 0)
        return 0;
    if (i != n && ck == k + 1)
        return 0;
 
    // Base case
    if (i == n)
    {
        if (ck == k + 1)
            return 1;
        else
            return 0;
    }
 
    // To check if a state
    // has been solved before
    if (v[i, ck])
        return dp[i, ck];
 
    // Sum of all the numbers from the beginning
    // of the array
    curr_sum += arr[i];
 
    // Setting the current state as solved
    v[i, ck] = true;
 
    // Recurrence relation
    dp[i,ck] = cntWays(arr, i + 1, ck, k, n, curr_sum);
    if (curr_sum == (sum / k) * ck)
        dp[i, ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum);
 
    // Returning solved state
    return dp[i, ck];
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, -1, 1, -1, 1, -1 };
    int n = arr.Length;
    int k = 2;
 
    // Function call to find the
    // sum of the array elements
    findSum(arr, n);
 
    // Print the number of ways
    Console.WriteLine(cntWays(arr, 0, 1, k, n, 0));
}
}
 
// This code contributed by Rajput-Ji

<script>
 
// Javascript implementation of the approach
 
var max_size = 20;
var max_k = 20
 
// Array to store the states of DP
var dp = Array.from(Array(max_size), ()=> Array(max_k));
 
// Array to check if a
// state has been solved before
var v = Array.from(Array(max_size), ()=> Array(max_k));
 
// To store the sum of
// the array elements
var sum = 0;
 
// Function to find the sum of
// all the array elements
function findSum(arr, n)
{
    for (var i = 0; i < n; i++)
        sum += arr[i];
}
 
// Function to return the number of ways
function cntWays(arr, i, ck, k, n, curr_sum)
{
    // If sum is not divisible by k
    // answer will be zero
    if (sum % k != 0)
        return 0;
    if (i != n && ck == k + 1)
        return 0;
 
    // Base case
    if (i == n) {
        if (ck == k + 1)
            return 1;
        else
            return 0;
    }
 
    // To check if a state
    // has been solved before
    if (v[i][ck])
        return dp[i][ck];
 
    // Sum of all the numbers from the beginning
    // of the array
    curr_sum += arr[i];
 
    // Setting the current state as solved
    v[i][ck] = 1;
 
    // Recurrence relation
    dp[i][ck] = cntWays(arr, i + 1, ck, k, n, curr_sum);
    if (curr_sum == (sum / k) * ck)
        dp[i][ck] += cntWays(arr, i + 1, ck + 1, k, n, curr_sum);
 
    // Returning solved state
    return dp[i][ck];
}
 
// Driver code
var arr = [1, -1, 1, -1, 1, -1];
var n = arr.length;
var k = 2;
// Function call to find the
// sum of the array elements
findSum(arr, n);
// Print the number of ways
document.write( cntWays(arr, 0, 1, k, n, 0));
 
 
</script>

2

Complejidad de tiempo: O(n*k)