DFS竟然和正解一样的时间!

### 代码1

``````//正解
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 110;

int n;
vector<LL> q[N];

//求解数字x的因子b的个数
int get(LL x, int b)
{
int res = 0;
while(x % b == 0)
{
res++;
x /= b;
}
return res;
}

int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
LL x;
cin >> x;
q[i] = {get(x, 2), -get(x, 3), x};
}

sort(q, q + n);

for(int i = 0; i < n; i++)
cout << q[i][2] << " ";
cout << endl;

return 0;
}
``````

### 代码2

``````//DFS
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 110;

int n;
LL q[N], res[N];
bool st[N];
unordered_map<LL,LL> s;

//索引为u位置的元素已经确定
void dfs(int u)
{
if(u == n - 1)
{
for(int i = 0; i < n; i++)
cout << res[i] << " ";
return;
}

LL a = res[u] * 2, b = res[u] / 3;
if(s.count(a) && !st[s[a]])
{
res[u+1] = a;
st[s[a]] = true;
dfs(u+1);
st[s[a]] = false;
}
else if(res[u] % 3 == 0 && s.count(b) && !st[s[b]])
{
res[u+1] = b;
st[s[b]] = true;
dfs(u+1);
st[s[b]] = false;
}

}

int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> q[i];
s.insert({q[i], i});
}

for(int i = 0; i < n; i++)
{
res[0] = q[i];
st[i] = true;//记录q中第i的元素已经被使用了
dfs(0);
st[i] = false;//恢复环境
}

}
``````