Check if N can be represented as sum of distinct powers of 3 | Java 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
class GFG { public static boolean PermuteAndFind ( int [ ] power , int idx , int SumSoFar , int target ) { if ( idx == power . length ) { if ( SumSoFar == target ) return true ; return false ; } boolean select = PermuteAndFind ( power , idx + 1 , SumSoFar , target ) ; boolean notselect = PermuteAndFind ( power , idx + 1 , SumSoFar + power [ idx ] , target ) ; return ( select notselect ) ; } public static void DistinctPowersOf3 ( int N ) { int [ ] power = new int [ 16 ] ; power [ 0 ] = 1 ; for ( int i = 1 ; i < 16 ; i ++ ) power [ i ] = 3 * power [ i - 1 ] ; boolean found = PermuteAndFind ( power , 0 , 0 , N ) ; if ( found == true ) { System . out . println ( " Yes " ) ; } else { System . out . println ( " No " ) ; } } public static void main ( String args [ ] ) { int N = 91 ; DistinctPowersOf3 ( N ) ; } }