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