869. 重新排序得到 2 的冪

給定正整數 N ，我們按任何順序（包括原始順序）將數字重新排序，注意其前導數字不能為零。

如果我們可以通過上述方式得到 2 的冪，返回 true；否則，返回 false。

• 示例 1：

輸入：1
輸出：true

• 示例 2：

輸入：10
輸出：false

• 示例 3：

輸入：16
輸出：true

• 示例 4：

輸入：24
輸出：false

• 示例 5：

輸入：46
輸出：true

解題思路

嘗試數字的所有排列方式，檢查每種排列方式是否能組成2的冪次

代碼

class Solution {Set<Integer> tar=new HashSet<>();public boolean reorderedPowerOf2(int n) {for (int i=0;i<31;i++){tar.add(1<<i);}String s=""+n;return dfsReorderedPowerOf2(s,new boolean[s.length()],0,new StringBuilder());}public boolean dfsReorderedPowerOf2(String s,boolean[] m,int cur,StringBuilder sb) {if (cur==s.length()){if (tar.contains(Integer.parseInt(sb.toString())))return true;return false;}boolean f=false;for (int i = 0; i < m.length; i++) {if (m[i]||cur==0&&s.charAt(i)=='0')continue;m[i]=true;sb.append(s.charAt(i));f|=dfsReorderedPowerOf2(s,m,cur+1,sb);sb.deleteCharAt(sb.length()-1);m[i]=false;}return f;}
}