Imprime todas las combinaciones de N elementos cambiando de signo de manera que su suma sea divisible por M

Dada una array de N enteros y un entero M. Puede cambiar el signo (positivo o negativo) de cualquier elemento de la array. La tarea es imprimir todas las combinaciones posibles de los elementos de la array que se pueden obtener cambiando el signo de los elementos de modo que su suma sea divisible por M. 

Nota : debe tomar todos los elementos de la array en cada combinación y en el mismo orden que los elementos presentes en la array. Sin embargo, puede cambiar el signo de los elementos.

Ejemplos: 

Entrada: a[] = {5, 6, 7}, M = 3 
Salida: 
-5-6-7 
+5-6+7 
-5+6-7 
+5+6+7

Entrada: a[] = {3, 5, 6, 8}, M = 5 
Salida: 
-3-5+6-8 
-3+5+6-8 
+3-5-6+8 
+3+5- 6+8

Enfoque: El concepto de conjunto potencia se utiliza aquí para resolver este problema. El uso de power-set genera todas las combinaciones posibles de signos que se pueden aplicar a la array de elementos. Si la suma obtenida es divisible por M, imprima la combinación. A continuación se muestran los pasos:  

  • Iterar para todas las combinaciones posibles de ‘+’ y ‘-‘ usando power set .
  • Iterar en los elementos de la array y si el j-ésimo bit de la izquierda está establecido, suponga que el elemento de la array es positivo y si el bit no está establecido, suponga que el elemento de la array es negativo. Consulte aquí para verificar si algún índice está configurado o no.
  • Si la suma es divisible por M, entonces vuelva a atravesar los elementos de la array e imprímalos junto con el signo (‘+’ o ‘-‘).

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

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to print all the combinations
void printCombinations(int a[], int n, int m)
{
 
    // Iterate for all combinations
    for (int i = 0; i < (1 << n); i++) {
        int sum = 0;
 
        // Initially 100 in binary if n is 3
        // as 1<<(3-1) = 100 in binary
        int num = 1 << (n - 1);
 
        // Iterate in the array and assign signs
        // to the array elements
        for (int j = 0; j < n; j++) {
 
            // If the j-th bit from left is set
            // take '+' sign
            if (i & num)
                sum += a[j];
            else
                sum += (-1 * a[j]);
 
            // Right shift to check if
            // jth bit is set or not
            num = num >> 1;
        }
 
        if (sum % m == 0) {
 
            // re-initialize
            num = 1 << (n - 1);
 
            // Iterate in the array elements
            for (int j = 0; j < n; j++) {
 
                // If the jth from left is set
                if ((i & num))
                    cout << "+" << a[j] << " ";
                else
                    cout << "-" << a[j] << " ";
 
                // right shift
                num = num >> 1;
            }
            cout << endl;
        }
    }
}
 
// Driver Code
int main()
{
    int a[] = { 3, 5, 6, 8 };
    int n = sizeof(a) / sizeof(a[0]);
    int m = 5;
 
    printCombinations(a, n, m);
    return 0;
}

Java

import java.io.*;
 
class GFG
{
     
// Function to print
// all the combinations
static void printCombinations(int a[],
                              int n, int m)
{
 
    // Iterate for all
    // combinations
    for (int i = 0;
             i < (1 << n); i++)
    {
        int sum = 0;
 
        // Initially 100 in binary
        // if n is 3 as
        // 1<<(3-1) = 100 in binary
        int num = 1 << (n - 1);
 
        // Iterate in the array
        // and assign signs to
        // the array elements
        for (int j = 0; j < n; j++)
        {
 
            // If the j-th bit
            // from left is set
            // take '+' sign
            if ((i & num) > 0)
                sum += a[j];
            else
                sum += (-1 * a[j]);
 
            // Right shift to check if
            // jth bit is set or not
            num = num >> 1;
        }
 
        if (sum % m == 0)
        {
 
            // re-initialize
            num = 1 << (n - 1);
 
            // Iterate in the
            // array elements
            for (int j = 0; j < n; j++)
            {
 
                // If the jth from
                // left is set
                if ((i & num) > 0)
                    System.out.print("+" +
                                     a[j] + " ");
                else
                    System.out.print("-" +
                                     a[j] + " ");
 
                // right shift
                num = num >> 1;
            }
             
        System.out.println();
        }
    }
}
 
// Driver code
public static void main(String args[])
{
    int a[] = { 3, 5, 6, 8 };
    int n = a.length;
    int m = 5;
 
    printCombinations(a, n, m);
}
}
 
// This code is contributed
// by inder_verma.

Python3

# Function to print
# all the combinations
def printCombinations(a, n, m):
 
    # Iterate for all
    # combinations
    for i in range(0, (1 << n)):
     
        sum = 0
 
        # Initially 100 in binary
        # if n is 3 as
        # 1<<(3-1) = 100 in binary
        num = 1 << (n - 1)
 
        # Iterate in the array
        # and assign signs to
        # the array elements
        for j in range(0, n):
         
            # If the j-th bit
            # from left is set
            # take '+' sign
            if ((i & num) > 0):
                sum += a[j]
            else:
                sum += (-1 * a[j])
 
            # Right shift to check if
            # jth bit is set or not
            num = num >> 1
 
        if (sum % m == 0):
         
            # re-initialize
            num = 1 << (n - 1)
 
            # Iterate in the
            # array elements
            for j in range(0, n):
 
                # If the jth from
                # left is set
                if ((i & num) > 0):
                    print("+", a[j], end = " ",
                                     sep = "")
                else:
                    print("-", a[j], end = " ",
                                     sep = "")
 
                # right shift
                num = num >> 1
            print("")
     
# Driver code
a = [ 3, 5, 6, 8 ]
n = len(a)
m = 5
printCombinations(a, n, m)
 
# This code is contributed
# by smita.

C#

// Print all the combinations
// of N elements by changing
// sign such that their sum
// is divisible by M
using System;
 
class GFG
{
     
// Function to print
// all the combinations
static void printCombinations(int []a,
                              int n, int m)
{
 
    // Iterate for all
    // combinations
    for (int i = 0;
             i < (1 << n); i++)
    {
        int sum = 0;
 
        // Initially 100 in binary
        // if n is 3 as
        // 1<<(3-1) = 100 in binary
        int num = 1 << (n - 1);
 
        // Iterate in the array
        // and assign signs to
        // the array elements
        for (int j = 0; j < n; j++)
        {
 
            // If the j-th bit
            // from left is set
            // take '+' sign
            if ((i & num) > 0)
                sum += a[j];
            else
                sum += (-1 * a[j]);
 
            // Right shift to check if
            // jth bit is set or not
            num = num >> 1;
        }
 
        if (sum % m == 0)
        {
 
            // re-initialize
            num = 1 << (n - 1);
 
            // Iterate in the
            // array elements
            for (int j = 0; j < n; j++)
            {
 
                // If the jth from
                // left is set
                if ((i & num) > 0)
                    Console.Write("+" +
                              a[j] + " ");
                else
                    Console.Write("-" +
                              a[j] + " ");
 
                // right shift
                num = num >> 1;
            }
             
        Console.Write("\n");
        }
    }
}
 
// Driver code
public static void Main()
{
    int []a = { 3, 5, 6, 8 };
    int n = a.Length;
    int m = 5;
 
    printCombinations(a, n, m);
}
}
 
// This code is contributed
// by Smitha.

PHP

<?php
// Function to print all the combinations
function printCombinations($a, $n, $m)
{
 
    // Iterate for all combinations
    for ($i = 0; $i < (1 << $n); $i++)
    {
        $sum = 0;
 
        // Initially 100 in binary if n 
        // is 3 as 1<<(3-1) = 100 in binary
        $num = 1 << ($n - 1);
 
        // Iterate in the array and assign
        // signs to the array elements
        for ($j = 0; $j < $n; $j++)
        {
 
            // If the j-th bit from left
            // is set take '+' sign
            if ($i & $num)
                $sum += $a[$j];
            else
                $sum += (-1 * $a[$j]);
 
            // Right shift to check if
            // jth bit is set or not
            $num = $num >> 1;
        }
 
        if ($sum % $m == 0)
        {
 
            // re-initialize
            $num = 1 << ($n - 1);
 
            // Iterate in the array elements
            for ($j = 0; $j < $n; $j++)
            {
 
                // If the jth from left is set
                if (($i & $num))
                    echo "+" , $a[$j] , " ";
                else
                    echo "-" , $a[$j] , " ";
 
                // right shift
                $num = $num >> 1;
            }
        echo "\n";
        }
    }
}
 
// Driver Code
$a = array( 3, 5, 6, 8 );
$n = sizeof($a);
$m = 5;
 
printCombinations($a, $n, $m);
 
// This code is contributed by ajit
?>

Javascript

<script>
 
// Function to print
// all the combinations
function printCombinations(a, n, m)
{
 
    // Iterate for all
    // combinations
    for(let i = 0; i < (1 << n); i++)
    {
        let sum = 0;
 
        // Initially 100 in binary
        // if n is 3 as
        // 1<<(3-1) = 100 in binary
        let num = 1 << (n - 1);
 
        // Iterate in the array
        // and assign signs to
        // the array elements
        for(let j = 0; j < n; j++)
        {
 
            // If the j-th bit
            // from left is set
            // take '+' sign
            if ((i & num) > 0)
                sum += a[j];
            else
                sum += (-1 * a[j]);
 
            // Right shift to check if
            // jth bit is set or not
            num = num >> 1;
        }
 
        if (sum % m == 0)
        {
 
            // Re-initialize
            num = 1 << (n - 1);
 
            // Iterate in the
            // array elements
            for(let j = 0; j < n; j++)
            {
 
                // If the jth from
                // left is set
                if ((i & num) > 0)
                    document.write("+" + a[j] + " ");
                else
                    document.write("-" + a[j] + " ");
 
                // Right shift
                num = num >> 1;
            }
            document.write("</br>");
        }
    }
}
 
// Driver code
let a = [ 3, 5, 6, 8 ];
let n = a.length;
let m = 5;
 
printCombinations(a, n, m);
 
// This code is contributed by mukesh07 
 
</script>
Producción: 

-3 -5 +6 -8 
-3 +5 +6 -8 
+3 -5 -6 +8 
+3 +5 -6 +8

 

Complejidad temporal: O(2 N * N), donde N es el número de elementos. 
 

Publicación traducida automáticamente

Artículo escrito por fathimabinthsalim y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *