解题代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define rep(i,a,n) for(int i = a; i <= n; i++)
const int N = 20;
int a[N];
int n,ans;
int st[N];
int check(int x){
int y = sqrt(x);
return y * y == x;
}
void dfs(int u, int last){
if(u == n){
ans++;
}else{
rep(i,0,n-1){
if(st[i])continue;//如果这个数已经被搜过了，就代表不用搜了
if(i && !st[i - 1] && a[i] == a[i - 1])continue;
//首先比第一个数大,
//然后处于递归的同一层，前一个肯定已经恢复现场了，
//最后判断是否和前一个相等.
if(!check(a[i] + last)) continue;//不满足条件
st[i] = 1;
dfs(u + 1,a[i]);
st[i] = 0;
}
}
}
int main(){
cin >> n;
rep(i,0,n - 1){
cin >> a[i];
}
sort(a,a + n);
rep(i,0,n -1){
if(!i|| a[i] != a[i - 1]){
st[i] = 1;
dfs(1,a[i]);//因为我们这里已经自己选择了一个数作为第一个元素，所以这里的1代表第二层
//所以递归的出口就是 u == n
st[i] = 0;
}
}
cout << ans << endl;
return 0;
}
dfs去重输出
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define rep(i,a,n) for(int i = a; i <= n; i++)
const int N = 20;
int a[N];
int n,ans;
int st[N];
int path[N];
void dfs(int u, int last){
if(u == n){
rep(i,0,n-1) cout<<path[i]<<" ";
puts("");
}else{
rep(i,0,n-1){
if(st[i])continue;
if(i && !st[i - 1] && a[i] == a[i - 1])continue;
st[i] = 1;
path[u] = a[i];
dfs(u + 1,a[i]);
st[i] = 0;
}
}
}
int main(){
cin >> n;
rep(i,0,n - 1) cin >> a[i];
sort(a,a + n);
rep(i,0,n -1){
if(!i|| a[i] != a[i - 1]){
st[i] = 1;
path[0] = a[i];
dfs(1,a[i]);
st[i] = 0;
}
}
return 0;
}
结果参考
