Encuentre si hay algún subconjunto de tamaño K con suma 0 en una array de -1 y +1

Dado un entero K y una array arr que contiene solo 1 y -1 , la tarea es encontrar si hay algún subconjunto de tamaño K cuyos elementos sean 0 .
Ejemplos: 
 

Entrada: arr[] = {1, -1, 1}, K = 2 
Salida: Sí 
{1, -1} es un subconjunto válido
Entrada: arr[] = {1, 1, -1, -1, 1} , K = 5 
Salida: No 
 

Acercarse: 
 

• Para que la suma sea 0 , tiene que haber igual número de 1 y -1 en el subconjunto.
• Si K es impar, ningún subconjunto satisfará la condición dada.
• De lo contrario, si K es par, entonces debemos elegir exactamente (K / 2) 1 y (K / 2) -1 para formar el subconjunto de modo que la suma de todos sus elementos sea 0
• Entonces, si K es par y el número de 1 ≥ K / 2 y el número de -1 ≥ K / 2 , imprima Sí ; de lo contrario, imprima No.

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

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

<script>
 
// Javascript 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)
{
    var i, count = 0;
    for (i = 0; i < n; i++)
        if (a[i] == 1)
            count++;
    return count;
}
 
function isSubset(arr, n, k)
{
    var countPos1 = countOnes(n, arr);
    var 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
var a = [1, 1, -1, -1, 1];
var n = a.length;
var k = 5;
if (isSubset(a, n, k))
  document.write( "Yes");
else
  document.write( "No");
 
// This code is contributed by famously.
</script>

No

Complejidad de tiempo: O(n)