1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// @Title: 重新排序得到 2 的幂 (Reordered Power of 2)
// @Author: 15816537946@163.com
// @Date: 2021-10-28 21:59:06
// @Runtime: 24 ms
// @Memory: 2 MB
func isPowerOf2(n int) bool {
	return n&(n-1) == 0
}

func reorderedPowerOf2(n int) bool {
	nums := []byte(strconv.Itoa(n))
	sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] })

	m := len(nums)
	vis := make([]bool, m) // 用于标记回溯

	var backtrack func(int, int) bool
	// 通过回溯拿到全排列
	backtrack = func(idx, num int) bool {
		if idx == m {
			return isPowerOf2(num)
		}

		for i, ch := range nums {
			// 不能有前导0
			if num == 0 && ch == '0' || vis[i] || i > 0 && !vis[i-1] && ch == nums[i-1] {
				continue
			}
			vis[i] = true
			if backtrack(idx+1, num*10+int(ch-'0')) {
				return true
			}
			vis[i] = false
		}

		return false
	}
	return backtrack(0, 0)

}