869. 重新排序得到2的幂

869. 重新排序得到 2 的幂

解题思路：

​ 这题是可以说是把两道题混合在了一起，分别是47. 全排列 II和231. 2 的幂，先通过前者求出全排列（回溯），当判断出现了符合要求的数后对后续进行剪枝操作即可。

• 注意Swap交换数字位置进行迭代之后要再通过Swap进行还原

以下是C++代码：

class Solution {
private:
    bool isSucc;
public:
    bool reorderedPowerOf2(int n) {
        //求全排列后逐个判断是否是2的幂
        isSucc=false;
        string str=to_string(n);
        sort(str.begin(),str.end()); //先进行排序(减少无用的匹配次数)
        GetAllOrder(str,0,str.size());
        return isSucc;
    }

    void GetAllOrder(string& str,int index,int length){
        if(index==length){
            if(isValid(str)) isSucc=true;
            return;
        }
        for(int i=index;i<length;i++){
            if(index==0&&str[i]=='0'){
                continue;//跳过首位为0
            }
            Swap(str,index,i);
            GetAllOrder(str,index+1,length);
            Swap(str,index,i);
            if(isSucc) return;
        }
    }

    bool isValid(const string& str){
        int n=atoi(str.c_str());
        return (n&(n-1))==0;
    }

    void Swap(string &str,int n,int m){
        char temp=str[n];
        str[n]=str[m];
        str[m]=temp;
    }


};