# 在-1和+1数组中查找是否有大小为K的子集且总和为0

2021年4月23日17:08:55 发表评论 524 次浏览

## 本文概述

{1, -1}是有效的子集

• 为了使和为0，在子集中必须有相同数量的1和-1。
• 如果K是奇数，那么没有一个子集满足给定的条件。
• 否则，如果K是偶数我们需要选择(K / 2) 1和(K / 2) -1来组成子集使所有元素之和为0
• 所以，如果K是偶数并且1的个数≥K / 2和-1的个数≥K / 2那么输出Yes否则输出No。

## C ++

``````//C++ program to find if there is a subset of size
//k with sum 0 in an array of -1 and +1
#include <bits/stdc++.h>
using namespace std;

//Function to return the number of 1's in the array
int countOnes( int n, int a[])
{
int i, count = 0;
for (i = 0; i <n; i++)
if (a[i] == 1)
count++;
return count;
}

bool isSubset( int arr[], int n, int k)
{
int countPos1 = countOnes(n, arr);
int countNeg1 = n - countPos1;

//If K is even and there are
//at least K/2 1's and -1's
return (k % 2 == 0 && countPos1>= k /2 &&
countNeg1>= k /2);
}

//Driver Program to test above function
int main()
{
int a[] = { 1, 1, -1, -1, 1 };
int n = sizeof (a) /sizeof (a[0]);
int k = 5;
if (isSubset(a, n, k))
cout <<"Yes" ;
else
cout <<"No" ;
return 0;
}``````

## Java

``````//Java program to find if there is a subset of size
//k with sum 0 in an array of -1 and +1

import java.io.*;

class GFG {

//Function to return the number of 1's in the array
static int countOnes( int n, int a[])
{
int i, count = 0 ;
for (i = 0 ; i <n; i++)
if (a[i] == 1 )
count++;
return count;
}

static boolean isSubset( int arr[], int n, int k)
{
int countPos1 = countOnes(n, arr);
int countNeg1 = n - countPos1;

//If K is even and there are
//at least K/2 1's and -1's
return (k % 2 == 0 && countPos1>= k /2 &&
countNeg1>= k /2 );
}

//Driver Program to test above function
public static void main (String[] args) {
int []a = { 1 , 1 , - 1 , - 1 , 1 };
int n = a.length;
int k = 5 ;
if (isSubset(a, n, k))
System.out.println( "Yes" );
else
System.out.println( "No" );
}
}
//This code is contributed by shs``````

## Python3

``````# Python3 program to find if there is
# a subset of size k with sum 0 in an
# array of -1 and +1

# Function to return the number of
# 1's in the array
def countOnes(n, a):

count = 0
for i in range ( 0 , n):
if a[i] = = 1 :
count + = 1
return count

def isSubset(arr, n, k):

countPos1 = countOnes(n, arr)
countNeg1 = n - countPos1

# If K is even and there are
# at least K/2 1's and -1's
return (k % 2 = = 0 and countPos1> = k //2 and
countNeg1> = k //2 )

# Driver Code
if __name__ = = "__main__" :

a = [ 1 , 1 , - 1 , - 1 , 1 ]
n = len (a)
k = 5

if isSubset(a, n, k) = = True :
print ( "Yes" )
else :
print ( "No" )

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

## C#

``````//C# program to find if there is
//a subset of size k with sum 0
//in an array of -1 and +1
using System;

class GFG
{

//Function to return the number
//of 1's in the array
static int countOnes( int n, int []a)
{
int i, count = 0;
for (i = 0; i <n; i++)
if (a[i] == 1)
count++;
return count;
}

static bool isSubset( int []arr, int n, int k)
{
int countPos1 = countOnes(n, arr);
int countNeg1 = n - countPos1;

//If K is even and there are
//at least K/2 1's and -1's
return (k % 2 == 0 && countPos1>= k /2 &&
countNeg1>= k /2);
}

//Driver Code
public static void Main ()
{
int []a = { 1, 1, -1, -1, 1 };
int n = a.Length;
int k = 5;
if (isSubset(a, n, k))
Console.WriteLine( "Yes" );
else
Console.WriteLine( "No" );
}
}

//This code is contributed by shs``````

## PHP

``````<?php
//PHP program to find if there
//is a subset of size k with
//sum 0 in an array of -1 and +1

//Function to return the number
//of 1's in the array
function countOnes( \$n , \$a )
{
\$count = 0;
for ( \$i = 0; \$i <\$n ; \$i ++)
if ( \$a [ \$i ] == 1)
\$count ++;
return \$count ;
}

function isSubset( \$arr , \$n , \$k )
{
\$countPos1 = countOnes( \$n , \$arr );
\$countNeg1 = \$n - \$countPos1 ;

//If K is even and there are
//at least K/2 1's and -1's
return ( \$k % 2 == 0 && \$countPos1>= \$k /2 &&
\$countNeg1>= \$k /2);
}

//Driver Code
\$a = array (1, 1, -1, -1, 1);
\$n = sizeof( \$a );
\$k = 5;

if (isSubset( \$a , \$n , \$k ))
echo "Yes" ;
else
echo "No" ;

//This code is contributed
//by Akanksha Rai
?>``````

``No``