869.重新排序得到 2 的幂

https://leetcode-cn.com/problems/reordered-power-of-2/

打表+dfs

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool
        s = set()
        i = 1
        while i <= 10 ** 9: #打表计算2的幂
            s.add(i)
            i *= 2
        cnt =[0] * 10   #统计0~9每个数字的个数
        length = 0  #数字n的长度
        while n:
            cnt[n%10] += 1
            n = n // 10
            length += 1
        #回溯函数，cur为当前数，l为当前数的长度
        def dfs(l, cur):
            if  l == length:    #递归出口：长度到达length
                return cur in s
            for i in range(10):   #从个位开始填数字
                if cnt[i] != 0:
                    cnt[i] -= 1
                    #注意：这里不能直接返回dfs结果，因为是找‘存在’，必须遍历完后续情况才能决定此处返回结果
                    # return dfs(l+1, cur*10+i)
                    #不能以0开头，即cur=0
                    #例外：初始时l=0，cur可以为0
                    if ((l == 0) or (l != 0 and cur != 0)) and dfs(l+1, cur*10+i):
                        return True     #后续递归也为true，向上层返回true
                    cnt[i] += 1     #恢复现场
            #另一个出口：没有可用数字
            return False
        return dfs(0,0)