在-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 +1import 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 = 5if isSubset(a, n, k) = = True : print ( "Yes" ) else : print ( "No" ) # This code is contributed # by Rituraj Jain

//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 ?>

输出如下：