一、题目
给定正整数N，我们按任何顺序（包括原始顺序）将 数字重新排序 ，注意其前导数字不能为零。 如果我们可以通过上述方式得到2的幂，返回 true；否则，返回false。
提示： 1 <= N <= 10^9
二、求解思路
题目要求对一个正整数进行重排序，并检查重排后的数字是否为2的幂。由于在int范围内，数字的长度有限，我们可以将数字n分解成单个数字，并允许它们自由组合。例如，对于数字123，自由组合的结果如下：
1. 123
2. 132
3. 213
4. 231
5. 312
6. 321
接下来，我们需要判断这些组合后的数字是否为2的幂。可以参考回溯算法模板来实现这一过程。
void backtrack(/* 原始参数 */) {// 终止条件(递归必须要有终止条件)if (/* 终止条件 */) {// 一些逻辑操作（可有可无，视情况而定）return;}for (int i = /* for循环开始的参数 */; i < /* for循环结束的参数 */; i++) {// 一些逻辑操作（可有可无，视情况而定）// 做出选择// 递归backtrack(/* 新的参数 */);// 一些逻辑操作（可有可无，视情况而定）// 撤销选择}
}因为有重复的数字，我们可以参照回溯算法解含有重复数字的全排列 II来对代码进行优化。
三、代码实现
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>bool isPowerOfTwo(int n) {return n > 0 && (n & (n - 1)) == 0;
}bool backtrack(std::vector<char>& numChar, std::vector<bool>& visit, int index, int num) {if (index == numChar.size()) {return isPowerOfTwo(num);}for (int i = 0; i < numChar.size(); ++i) {if (num == 0 && numChar[i] == '0') {continue;}if (visit[i]) {continue;}if (i > 0 && numChar[i - 1] == numChar[i] && visit[i - 1]) {continue;}visit[i] = true;if (backtrack(numChar, visit, index + 1, num * 10 + numChar[i] - '0')) {return true;}visit[i] = false;}return false;
}bool reorderedPowerOf2(int n) {std::string numStr = std::to_string(n);std::vector<char> numChar(numStr.begin(), numStr.end());std::sort(numChar.begin(), numChar.end());std::vector<bool> visit(numChar.size(), false);return backtrack(numChar, visit, 0, 0);
}int main() {int n = 123; // 你可以修改这个值来测试不同的输入if (reorderedPowerOf2(n)) {std::cout << n << " can be reordered to a power of 2." << std::endl;} else {std::cout << n << " cannot be reordered to a power of 2." << std::endl;}return 0;
}排序比较方法：
这种比较好理解，就是先把 数字转化为数组比如numChar ，然后再把int范围内所有 2 的幂也转化为数组，然后判断numChar和2的幂转化的数组是否一样。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>bool reorderedPowerOf2(int n) {// 先把数字转化为字符std::string numStr = std::to_string(n);std::vector<char> numChar(numStr.begin(), numStr.end());// 对字符进行排序std::sort(numChar.begin(), numChar.end());for (int i = 0; i < 31; i++) {// 把2的幂转化为字符，然后排序std::string bitStr = std::to_string(1 << i);std::vector<char> bitChar(bitStr.begin(), bitStr.end());std::sort(bitChar.begin(), bitChar.end());// 比较这两个数组if (numChar == bitChar) {return true;}}return false;
}int main() {int n = 123; // 你可以修改这个值来测试不同的输入if (reorderedPowerOf2(n)) {std::cout << n << " can be reordered to a power of 2." << std::endl;} else {std::cout << n << " cannot be reordered to a power of 2." << std::endl;}return 0;
}
