Given an array of N integers and an integer M. You can change the sign(positive or negative) of any element in the array. The task is to print all possible combinations of the array elements that can be obtained by changing the sign of the elements such that their sum is divisible by M.
Note: You have to take all of the array elements in each combination and in the same order as the elements present in the array. However, you can change the sign of elements.
Examples:
Input: a[] = {5, 6, 7}, M = 3
Output:
-5-6-7
+5-6+7
-5+6-7
+5+6+7Input: a[] = {3, 5, 6, 8}, M = 5
Output:
-3-5+6-8
-3+5+6-8
+3-5-6+8
+3+5-6+8
Approach: The concept of power set is used here to solve this problem. Using power-set generate all possible combinations of signs that can be applied to the array of elements. If the sum obtained is divisible by M, then print the combination. Below are the steps:
- Iterate for all possible combinations of ‘+’ and ‘-‘ using power set.
- Iterate on the array elements and if the j-th bit from left is set, then assume the array element to be positive and if the bit is not set, then assume the array element to be negative. Refer here to check if bit any index is set or not.
- If the sum is divisible by M, then the again traverse the array elements and print them along with sign( ‘+’ or ‘-‘ ).
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to print all the combinationsvoid 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 Codeint 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 combinationsstatic 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 codepublic 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 combinationsdef 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 codea = [ 3, 5, 6, 8 ]n = len(a)m = 5printCombinations(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 Musing System;class GFG{ // Function to print// all the combinationsstatic 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 codepublic 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 combinationsfunction 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 codelet a = [ 3, 5, 6, 8 ];let n = a.length;let m = 5;printCombinations(a, n, m);// This code is contributed by mukesh07 </script> |
Output
-3 -5 +6 -8 -3 +5 +6 -8 +3 -5 -6 +8 +3 +5 -6 +8
Time Complexity: O(2N * N), where N is the number of elements.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
