Check if N can be represented as sum of distinct powers of 3 | 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 ; Driver Code
def PermuteAndFind ( power , idx , SumSoFar , target ) : NEW_LINE INDENT if ( idx == len ( power ) ) : NEW_LINE INDENT if ( SumSoFar == target ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT select = PermuteAndFind ( power , idx + 1 , SumSoFar , target ) NEW_LINE notselect = PermuteAndFind ( power , idx + 1 , SumSoFar + power [ idx ] , target ) NEW_LINE return ( select or notselect ) NEW_LINE DEDENT def DistinctPowersOf3 ( N ) : NEW_LINE INDENT power = [ 0 for x in range ( 16 ) ] NEW_LINE power [ 0 ] = 1 NEW_LINE for i in range ( 1 , 16 ) : NEW_LINE INDENT power [ i ] = 3 * power [ i - 1 ] NEW_LINE DEDENT found = PermuteAndFind ( power , 0 , 0 , N ) NEW_LINE if ( found == True ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT N = 91 NEW_LINE DistinctPowersOf3 ( N ) NEW_LINE