Check if N can be represented as sum of distinct powers of 3 | C ++ program for the above approach ; Function to try all permutations of distinct powers ; Base Case ; If the distinct powers sum is obtained ; Otherwise ; If current element not selected in power [ ] ; If current element selected in power [ ] ; Return 1 if any permutation found ; Function to check the N can be represented as the sum of the distinct powers of 3 ; Stores the all distincts powers of three to [ 0 , 15 ] ; Function Call ; print ; Driven Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool PermuteAndFind ( vector < long > power , int idx , long SumSoFar , int target ) { if ( idx == power . size ( ) ) { if ( SumSoFar == target ) return true ; return false ; } bool select = PermuteAndFind ( power , idx + 1 , SumSoFar , target ) ; bool notselect = PermuteAndFind ( power , idx + 1 , SumSoFar + power [ idx ] , target ) ; return ( select notselect ) ; } void DistinctPowersOf3 ( int N ) { vector < long > power ( 16 ) ; power [ 0 ] = 1 ; for ( int i = 1 ; i < 16 ; i ++ ) power [ i ] = 3 * power [ i - 1 ] ; bool found = PermuteAndFind ( power , 0 , 0L , N ) ; if ( found == true ) { cout << " Yes " ; } else { cout << " No " ; } } int main ( ) { int N = 91 ; DistinctPowersOf3 ( N ) ; return 0 ; }