Surgen varias situaciones al resolver un problema en el que necesitamos iterar sobre todas las combinaciones posibles de una array. En este artículo, discutiremos el método de usar bits para hacerlo.
Con el propósito de explicar, considere la siguiente pregunta:
Dada una array b[] = {2, 1, 4}. La tarea es comprobar si existe alguna combinación de elementos de este arreglo cuya suma de elementos sea igual a k = 6.
Solución usando operaciones de bits :
como hay 3 elementos en esta array, necesitamos 3 bits para representar cada uno de los números. Un bit puesto a 1 correspondiente al elemento significa que se incluye al calcular la suma, y no si es 0.
Las posibles combinaciones son:
000 : No element is selected. 001 : 4 is selected. 010 : 1 is selected. 011 : 1 and 4 are selected. 100 : 2 is selected. 101 : 2 and 4 are selected. 110 : 2 and 1 are selected. 111 : All elements are selected.
Por lo tanto, el rango requerido para acceder a todos estos bits es de 0 a 7. Iteramos sobre cada bit de cada una de las combinaciones posibles y verificamos para cada combinación si la suma de los elementos elegidos es igual a la suma requerida o no.
Ejemplos:
Input : A = {3, 4, 1, 2} and k = 6
Output : YES
Here, the combination of using 3, 1 and 2 yields
the required sum.
Input : A = {3, 4, 1, 2} and k = 11
Output : NO
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to iterate over all possible
// combinations of array elements
#include <bits/stdc++.h>
using namespace std;
// Function to check if any combination of
// elements of the array sums to k
bool checkSum(int a[], int n, int k)
{
// Flag variable to check if
// sum exists
int flag = 0;
// Calculate number of bits
int range = (1 << n) - 1;
// Generate combinations using bits
for (int i = 0; i <= range; i++) {
int x = 0, y = i, sum = 0;
while (y > 0) {
if (y & 1 == 1) {
// Calculate sum
sum = sum + a[x];
}
x++;
y = y >> 1;
}
// If sum is found, set flag to 1
// and terminate the loop
if (sum == k)
return true;
}
return false;
}
// Driver Code
int main()
{
int k = 6;
int a[] = { 3, 4, 1, 2 };
int n = sizeof(a)/sizeof(a[0]);
if (checkSum(a, n, k))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to iterate over all possible
// combinations of array elements
class GFG
{
// Function to check if any combination
// of elements of the array sums to k
static boolean checkSum(int a[], int n, int k)
{
// Flag variable to check if
// sum exists
int flag = 0;
// Calculate number of bits
int range = (1 << n) - 1;
// Generate combinations using bits
for (int i = 0; i <= range; i++)
{
int x = 0, y = i, sum = 0;
while (y > 0)
{
if ((y & 1) == 1)
{
// Calculate sum
sum = sum + a[x];
}
x++;
y = y >> 1;
}
// If sum is found, set flag to 1
// and terminate the loop
if (sum == k)
return true;
}
return false;
}
// Driver Code
public static void main(String[] args)
{
int k = 6;
int a[] = { 3, 4, 1, 2 };
int n = a.length;
if (checkSum(a, n, k))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed
// by Code_Mech
Python3
# Python 3 program to iterate over all
# possible combinations of array elements
# Function to check if any combination of
# elements of the array sums to k
def checkSum(a, n, k):
# Flag variable to check if
# sum exists
flag = 0
# Calculate number of bits
range__ = (1 << n) - 1
# Generate combinations using bits
for i in range(range__ + 1):
x = 0
y = i
sum = 0
while (y > 0):
if (y & 1 == 1):
# Calculate sum
sum = sum + a[x]
x += 1
y = y >> 1
# If sum is found, set flag to 1
# and terminate the loop
if (sum == k):
return True
return False
# Driver Code
if __name__ == '__main__':
k = 6
a = [3, 4, 1, 2]
n = len(a)
if (checkSum(a, n, k)):
print("Yes")
else:
print("No")
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to iterate over all possible
// combinations of array elements
using System;
class GFG
{
// Function to check if any combination
// of elements of the array sums to k
static bool checkSum(int[] a, int n, int k)
{
// Flag variable to check if
// sum exists
int // C# program to iterate over all possible
// combinations of array elements
using System;
class GFG
{
// Function to check if any combination
// of elements of the array sums to k
static bool checkSum(int[] a, int n, int k)
{
// Flag variable to check if
// sum exists
int flag = 0;
// Calculate number of bits
int range = (1 << n) - 1;
// Generate combinations using bits
for (int i = 0; i <= range; i++)
{
int x = 0, y = i, sum = 0;
while (y > 0)
{
if ((y & 1) == 1)
{
// Calculate sum
sum = sum + a[x];
}
x++;
y = y >> 1;
}
// If sum is found, set flag to 1
// and terminate the loop
if (sum == k)
return true;
}
return false;
}
// Driver Code
public static void Main()
{
int k = 6;
int[] a = { 3, 4, 1, 2 };
int n = a.Length;
if (checkSum(a, n, k))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed
// by Code_Mech
PHP
<?php
// PHP program to iterate over all possible
// combinations of array elements
// Function to check if any combination of
// elements of the array sums to k
function checkSum($a, $n, $k)
{
// Flag variable to check if
// sum exists
$flag = 0;
// Calculate number of bits
$range = (1 << $n) - 1;
// Generate combinations using bits
for ($i = 0; $i <= $range; $i++)
{
$x = 0;
$y = $i;
$sum = 0;
while ($y > 0)
{
if ($y & 1 == 1)
{
// Calculate sum
$sum = $sum + $a[$x];
}
$x++;
$y = $y >> 1;
}
// If sum is found, set flag to 1
// and terminate the loop
if ($sum == $k)
return true;
}
return false;
}
// Driver Code
$k = 6;
$a = array( 3, 4, 1, 2 );
$n = sizeof($a);
if (checkSum($a, $n, $k))
echo "Yes";
else
echo "No";
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript program to iterate over all possible
// combinations of array elements
// Function to check if any combination
// of elements of the array sums to k
function checkSum(a, n, k)
{
// Flag variable to check if
// sum exists
let flag = 0;
// Calculate number of bits
let range = (1 << n) - 1;
// Generate combinations using bits
for (let i = 0; i <= range; i++)
{
let x = 0, y = i, sum = 0;
while (y > 0)
{
if ((y & 1) == 1)
{
// Calculate sum
sum = sum + a[x];
}
x++;
y = y >> 1;
}
// If sum is found, set flag to 1
// and terminate the loop
if (sum == k)
return true;
}
return false;
}
let k = 6;
let a = [ 3, 4, 1, 2 ];
let n = a.length;
if (checkSum(a, n, k))
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
Complejidad de tiempo : 2 (número de bits)
Publicación traducida automáticamente
Artículo escrito por noob_coders_ka_baap y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA