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

本文概述

• C ++
• Java
• Python3
• C#
• PHP

给定一个整数K和一个仅包含1和-1的数组arr，任务是找出是否存在任何大小为K的子集，其元素之和为0。

例子：

输入：arr [] = {1, -1, 1}, K = 2
输出：YES
{1, -1}是有效的子集
输入：arr [] = {1, 1, -1, -1, 1} , K = 5
输出：NO

方法：

• 为了使和为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

时间复杂度：O(n)

---