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
def printCombinations ( a , n , m ) : NEW_LINE INDENT for i in range ( 0 , ( 1 << n ) ) : NEW_LINE INDENT sum = 0 NEW_LINE num = 1 << ( n - 1 ) NEW_LINE for j in range ( 0 , n ) : NEW_LINE INDENT if ( ( i & num ) > 0 ) : NEW_LINE INDENT sum += a [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT sum += ( - 1 * a [ j ] ) NEW_LINE DEDENT num = num >> 1 NEW_LINE DEDENT if ( sum % m == 0 ) : NEW_LINE INDENT num = 1 << ( n - 1 ) NEW_LINE for j in range ( 0 , n ) : NEW_LINE INDENT if ( ( i & num ) > 0 ) : NEW_LINE INDENT print ( " + " , a [ j ] , end = " ▁ " , sep = " " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " - " , a [ j ] , end = " ▁ " , sep = " " ) NEW_LINE DEDENT num = num >> 1 NEW_LINE DEDENT print ( " " ) NEW_LINE DEDENT DEDENT DEDENT a = [ 3 , 5 , 6 , 8 ] NEW_LINE n = len ( a ) NEW_LINE m = 5 NEW_LINE printCombinations ( a , n , m ) NEW_LINE