# 检查是否有可能以相等的总和划分k个子数组

2021年4月15日19:09:48 发表评论 606 次浏览

## 本文概述

``````Input : arr[] = { 1, 4, 2, 3, 5 } K = 3
Output : Yes
Explanation :
Three possible partitions which have equal sum :
(1 + 4), (2 + 3) and (5)

Input : arr[] = { 1, 1, 2, 2 } K = 2
Output : No``````

1.对于特定的K, 每个子数组应具有所需的总和= total_sum /K。

2.从第0个下标开始，开始比较前缀sum，只要它等于sum，它就意味着一个子数组的结束(假设是在下标j处)。

3.从(j + 1)第一个索引中，找到另一个合适的i，其sum (prefix_sum[i] - prefix_sum[j])等于所需的sum。这个过程一直进行，直到找到所需数量的连续子数组，即K。

4.如果在任意下标处，任何子数组的和大于所需的和，则退出循环，因为每个子数组都应该包含一个相等的和。

## C++

``````//CPP Program to check if array
//can be split into K contiguous
//subarrays each having equal sum
#include <bits/stdc++.h>
using namespace std;

//function returns true to it is possible to
//create K contiguous partitions each having
//equal sum, otherwise false
bool KpartitionsPossible( int arr[], int n, int K)
{
//Creating and filling prefix sum array
int prefix_sum[n];
prefix_sum[0] = arr[0];
for ( int i = 1; i <n; i++)
prefix_sum[i] =  prefix_sum[i - 1] + arr[i];

//return false if total_sum is not
//divisible by K
int total_sum = prefix_sum[n-1];
if (total_sum % K != 0)
return false ;

//a temporary variable to check
//there are exactly K partitions
int temp = 0;

int pos = -1;
for ( int i = 0; i <n; i++)
{
//find suitable i for which first
//partition have the required sum
//and then find next partition and so on
if (prefix_sum[i] - (pos == -1 ? 0 :
prefix_sum[pos]) == total_sum /K)
{
pos = i;
temp++;
}

//if it becomes greater than
//required sum break out
else if (prefix_sum[i] - prefix_sum[pos]>
total_sum /K)
break ;
}

//check if temp has reached to K
return (temp == K);
}

//Driver Code
int main()
{
int arr[] = { 4, 4, 3, 5, 6, 2 };
int n = sizeof (arr) /sizeof (arr[0]);

int K = 3;
if (KpartitionsPossible(arr, n, K))
cout <<"Yes" ;
else
cout <<"No" ;
return 0;
}``````

## Java

``````//Java Program to check if an array
//can be split into K contiguous
//subarrays each having equal sum
public class GfG{

//Function returns true to it is possible to
//create K contiguous partitions each having
//equal sum, otherwise false
static boolean KpartitionsPossible( int arr[], int n, int K)
{
//Creating and filling prefix sum array
int prefix_sum[] = new int [n];
prefix_sum[ 0 ] = arr[ 0 ];
for ( int i = 1 ; i <n; i++)
prefix_sum[i] = prefix_sum[i - 1 ] + arr[i];

//return false if total_sum is not divisible by K
int total_sum = prefix_sum[n- 1 ];
if (total_sum % K != 0 )
return false ;

//a temporary variable to check
//there are exactly K partitions
int temp = 0 , pos = - 1 ;

for ( int i = 0 ; i <n; i++)
{
//find suitable i for which first
//partition have the required sum
//and then find next partition and so on
if (prefix_sum[i] - (pos == - 1 ? 0 :
prefix_sum[pos]) == total_sum /K)
{
pos = i;
temp++;
}

//if it becomes greater than
//required sum break out
else if (prefix_sum[i] - (pos == - 1 ? 0 :
prefix_sum[pos])> total_sum /K)
break ;
}

//check if temp has reached to K
return (temp == K);
}

public static void main(String []args){

int arr[] = { 4 , 4 , 3 , 5 , 6 , 2 };
int n = arr.length;

int K = 3 ;
if (KpartitionsPossible(arr, n, K))
System.out.println( "Yes" );
else
System.out.println( "No" );
}
}

//This code is contributed by Rituraj Jain``````

## Python3

``````# Python 3 Program to check if array
# can be split into K contiguous
# subarrays each having equal sum

# function returns true to it is possible to
# create K contiguous partitions each having
# equal sum, otherwise false
def KpartitionsPossible(arr, n, K):

# Creating and filling prefix sum array
prefix_sum = [ 0 for i in range (n)]
prefix_sum[ 0 ] = arr[ 0 ]
for i in range ( 1 , n, 1 ):
prefix_sum[i] = prefix_sum[i - 1 ] + arr[i]

# return false if total_sum is not
# divisible by K
total_sum = prefix_sum[n - 1 ]
if (total_sum % K ! = 0 ):
return False

# a temporary variable to check
# there are exactly K partitions
temp = 0

pos = - 1
for i in range ( 0 , n, 1 ):

# find suitable i for which first
# partition have the required sum
# and then find next partition and so on
if (pos = = - 1 ):
sub = 0
else :
sub = prefix_sum[pos]
if (prefix_sum[i] - sub = = total_sum /K) :
pos = i
temp + = 1

# if it becomes greater than
# required sum break out
elif (prefix_sum[i] -
prefix_sum[pos]> total_sum /K):
break

# check if temp has reached to K
return (temp = = K)

# Driver Code
if __name__ = = '__main__' :
arr = [ 4 , 4 , 3 , 5 , 6 , 2 ]
n = len (arr)

K = 3
if (KpartitionsPossible(arr, n, K)):
print ( "Yes" )
else :
print ( "No" )

# This code is contributed by
# Shashank_Sharma``````

## C#

``````//C# Program to check if an array
//can be split into K contiguous
//subarrays each having equal sum
using System;

class GfG
{

//Function returns true to it is possible to
//create K contiguous partitions each having
//equal sum, otherwise false
static bool KpartitionsPossible( int [] arr, int n, int K)
{
//Creating and filling prefix sum array
int [] prefix_sum = new int [n];
prefix_sum[0] = arr[0];
for ( int i = 1; i <n; i++)
prefix_sum[i] = prefix_sum[i - 1] + arr[i];

//return false if total_sum is not divisible by K
int total_sum = prefix_sum[n-1];
if (total_sum % K != 0)
return false ;

//a temporary variable to check
//there are exactly K partitions
int temp = 0, pos = -1;

for ( int i = 0; i <n; i++)
{
//find suitable i for which first
//partition have the required sum
//and then find next partition and so on
if (prefix_sum[i] - (pos == -1 ? 0 :
prefix_sum[pos]) == total_sum /K)
{
pos = i;
temp++;
}

//if it becomes greater than
//required sum break out
else if (prefix_sum[i] - (pos == -1 ? 0 :
prefix_sum[pos])> total_sum /K)
break ;
}

//check if temp has reached to K
return (temp == K);
}

//Driver code
public static void Main()
{

int [] arr = { 4, 4, 3, 5, 6, 2 };
int n = arr.Length;

int K = 3;
if (KpartitionsPossible(arr, n, K))
Console.WriteLine( "Yes" );
else
Console.WriteLine( "No" );
}
}

//This code is contributed by ChitraNayal``````

## PHP

``````<?php
//PHP Program to check if array
//can be split into K contiguous
//subarrays each having equal sum

//function returns true to
//it is possible to create
//K contiguous partitions
//each having equal sum, //otherwise false
function KpartitionsPossible( \$arr , \$n , \$K )
{
//Creating and filling
//prefix sum array
\$prefix_sum = Array();
\$prefix_sum [0] = \$arr [0];
for ( \$i = 1; \$i <\$n ; \$i ++)
\$prefix_sum [ \$i ] = \$prefix_sum [ \$i - 1] +
\$arr [ \$i ];

//return false if total_sum
//is not divisible by K
\$total_sum = \$prefix_sum [ \$n - 1];
if ( \$total_sum % \$K != 0)
return false;

//a temporary variable to
//check there are exactly
//K partitions
\$temp = 0;

\$pos = -1;
for ( \$i = 0; \$i <\$n ; \$i ++)
{
//find suitable i for which
//first partition have the
//required sum and then find
//next partition and so on
if ( \$prefix_sum [ \$i ] - ( \$pos == -1 ? 0 :
\$prefix_sum [ \$pos ]) ==
(int) \$total_sum /\$K )
{
\$pos = \$i ;
\$temp ++;
}
}

//check if temp has
//reached to K
return ( \$temp == \$K );
}

//Driver Code
\$arr = array (4, 4, 3, 5, 6, 2);
\$n = sizeof( \$arr ) ;

\$K = 3;
if (KpartitionsPossible( \$arr , \$n , \$K ))
echo "Yes" ;
else
echo "No" ;

//This code is contributed by m_kit
?>``````

``Yes``

## C++

``````//CPP Program to check if array
//can be split into K contiguous
//subarrays each having equal sum
#include <bits/stdc++.h>
using namespace std;

//function returns true to it is possible to
//create K contiguous partitions each having
//equal sum, otherwise false
int KpartitionsPossible( int arr[], int n, int k)
{
int sum = 0;
int count = 0;

//calculate the sum of the array
for ( int i = 0; i <n; i++)
sum = sum + arr[i];

if (sum % k != 0)
return 0;

sum = sum /k;
int ksum = 0;

//ksum denotes the sum of each subarray
for ( int i = 0; i <n; i++)
{
ksum=ksum + arr[i];

//one subarray is found
if (ksum == sum)
{
//to locate another
ksum = 0;
count++;
}

}

if (count == k)
return 1;
else
return 0;

}

//Driver code
int main() {

int arr[] = { 1, 1, 2, 2};
int k = 2;
int n = sizeof (arr) /sizeof (arr[0]);
if (KpartitionsPossible(arr, n, k) == 0)
cout <<"Yes" ;
else
cout<<"No" ;
return 0;

}``````

## Java

``````//Java Program to check if array
//can be split into K contiguous
//subarrays each having equal sum

public class GFG {

//function returns true to it is possible to
//create K contiguous partitions each having
//equal sum, otherwise false
static int KpartitionsPossible( int arr[], int n, int k) {
int sum = 0 ;
int count = 0 ;

//calculate the sum of the array
for ( int i = 0 ; i <n; i++) {
sum = sum + arr[i];
}

if (sum % k != 0 ) {
return 0 ;
}

sum = sum /k;
int ksum = 0 ;

//ksum denotes the sum of each subarray
for ( int i = 0 ; i <n; i++) {
ksum = ksum + arr[i];

//one subarray is found
if (ksum == sum) {
//to locate another
ksum = 0 ;
count++;
}

}

if (count == k) {
return 1 ;
} else {
return 0 ;
}

}

//Driver Code
public static void main(String[] args) {

int arr[] = { 1 , 1 , 2 , 2 };
int k = 2 ;
int n = arr.length;

if (KpartitionsPossible(arr, n, k) == 0 ) {
System.out.println( "Yes" );
} else {
System.out.println( "No" );
}
}

}

/*This code is contributed by PrinciRaj1992*/``````

## Python3

``````# Python3 Program to check if array
# can be split into K contiguous
# subarrays each having equal sum

# Function returns true to it is possible
# to create K contiguous partitions each
# having equal sum, otherwise false
def KpartitionsPossible(arr, n, k) :

sum = 0
count = 0

# calculate the sum of the array
for i in range (n) :
sum = sum + arr[i]

if ( sum % k ! = 0 ) :
return 0

sum = sum //k
ksum = 0

# ksum denotes the sum of each subarray
for i in range (n) :
ksum = ksum + arr[i]

# one subarray is found
if (ksum = = sum ) :

# to locate another
ksum = 0
count + = 1

if (count = = k) :
return 1
else :
return 0

# Driver code
if __name__ = = "__main__" :

arr = [ 1 , 1 , 2 , 2 ]
k = 2
n = len (arr)
if (KpartitionsPossible(arr, n, k) = = 0 ) :
print ( "Yes" )
else :
print ( "No" )

# This code is contributed by Ryuga``````

## C#

``````//C# Program to check if array
//can be split into K contiguous
//subarrays each having equal sum

using System;
public class GFG{

//function returns true to it is possible to
//create K contiguous partitions each having
//equal sum, otherwise false
static int KpartitionsPossible( int []arr, int n, int k) {
int sum = 0;
int count = 0;

//calculate the sum of the array
for ( int i = 0; i <n; i++) {
sum = sum + arr[i];
}

if (sum % k != 0) {
return 0;
}

sum = sum /k;
int ksum = 0;

//ksum denotes the sum of each subarray
for ( int i = 0; i <n; i++) {
ksum = ksum + arr[i];

//one subarray is found
if (ksum == sum) {
//to locate another
ksum = 0;
count++;
}

}

if (count == k) {
return 1;
} else {
return 0;
}

}

//Driver Code
public static void Main() {

int []arr = {1, 1, 2, 2};
int k = 2;
int n = arr.Length;

if (KpartitionsPossible(arr, n, k) == 0) {
Console.Write( "Yes" );
} else {
Console.Write( "No" );
}
}

}

/*This code is contributed by PrinciRaj1992*/``````

## PHP

``````<?php
//PHP Program to check if array
//can be split into K contiguous
//subarrays each having equal sum

//function returns true to it is possible to
//create K contiguous partitions each having
//equal sum, otherwise false
function KpartitionsPossible( \$arr , \$n , \$k )
{
\$sum = 0;
\$count = 0;

//calculate the sum of the array
for ( \$i = 0; \$i <\$n ; \$i ++)
\$sum = \$sum + \$arr [ \$i ];

if ( \$sum % \$k != 0)
return 0;

\$sum = \$sum /\$k ;
\$ksum = 0;

//ksum denotes the sum of each subarray
for ( \$i = 0; \$i <\$n ; \$i ++)
{
\$ksum = \$ksum + \$arr [ \$i ];

//one subarray is found
if ( \$ksum == \$sum )
{
//to locate another
\$ksum = 0;
\$count ++;
}
}

if ( \$count == \$k )
return 1;
else
return 0;

}

//Driver code
\$arr = array (1, 1, 2, 2);
\$k = 2;
\$n = count ( \$arr );
if (KpartitionsPossible( \$arr , \$n , \$k ) == 0)
echo "Yes" ;
else
echo "No" ;

//This code is contributed by
//Rajput-Ji
?>``````

``Yes``