Count ways to represent N as sum of powers of 2 | C ++ program for above implementation ; Base Cases ; Check if 2 ^ k can be used as one of the numbers or not ; Otherwise ; Count number of ways to N using 2 ^ k - 1 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int numberOfWays ( int n , int k ) { if ( n == 0 ) return 1 ; if ( k == 0 ) return 1 ; if ( n >= pow ( 2 , k ) ) { int curr_val = pow ( 2 , k ) ; return numberOfWays ( n - curr_val , k ) + numberOfWays ( n , k - 1 ) ; } else return numberOfWays ( n , k - 1 ) ; } int main ( ) { int n = 4 ; int k = log2 ( n ) ; cout << numberOfWays ( n , k ) << endl ; }