Represent n as the sum of exactly k powers of two | Set 2 | Function to print k numbers which are powers of two and whose sum is equal to n ; Initialising the sum with k ; Initialising an array A with k elements and filling all elements with 1 ; Iterating A [ ] from k - 1 to 0 ; Update sum and A [ i ] till sum + A [ i ] is less than equal to n ; Impossible to find the combination ; Possible solution is stored in A [ ] ; Driver code
def FindAllElements ( n , k ) : NEW_LINE INDENT sum = k NEW_LINE A = [ 1 for i in range ( k ) ] NEW_LINE i = k - 1 NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT while ( sum + A [ i ] <= n ) : NEW_LINE INDENT sum += A [ i ] NEW_LINE A [ i ] *= 2 NEW_LINE DEDENT i -= 1 NEW_LINE DEDENT if ( sum != n ) : NEW_LINE INDENT print ( " Impossible " ) NEW_LINE DEDENT else : NEW_LINE INDENT for i in range ( 0 , k , 1 ) : NEW_LINE INDENT print ( A [ i ] , end = ' ▁ ' ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 12 NEW_LINE k = 6 NEW_LINE FindAllElements ( n , k ) NEW_LINE DEDENT