对于子集的深度搜索的话,比全排列问题更加简便了,其回溯时,查找的其他子节点少了很多,有点像是全排列的树被减去了很多很多的节点,由全排列变成了组合问题,
下面的两种解法一种是基于多叉树,另一种是基于二叉树的,基于二叉树的dfs跟位运算的思想基本一致,
实话实说还是位运算简单易懂,又高效
代码如下
算法1
(多叉树的dfs) $O(2^n)$
C++ 代码
#include<iostream>
#include<vector>
#include<set>
using namespace std;
int fac(int x) {
if (x == 0) return 1;
return x*fac(x - 1);
}
void dfs(int* f, int begin, set<int>& res, int sum) {
if(sum>0)res.insert(sum);
for (int i = begin; i < 10; i++) { //按照构建全排列的方式,但是每次的起点只能是比当前的节点靠后
int now = f[i];
sum += now;
dfs(f, i + 1, res, sum); //对i+1进行下移操作,确保不重复
sum -= now;
}
}
int main() {
int n;
int f[10];
set<int> res;
for (int i = 0; i < 10; i++) {
f[i] = fac(i);
}
dfs(f, 0, res, 0);
//for (auto i : res) cout << i << ' ';
while (cin >> n) {
if (n < 0) return 0;
if (res.count(n)) {
cout << "YES" << endl;
}
else cout << "NO" << endl;
}
}
算法2
(基于二叉树的解法) $O(2^n)$
C++ 代码
#include<iostream>
#include<set>
using namespace std;
int fac(int n) {
if (n == 0) return 1;
return n * fac(n - 1);
}
void dfs(int* f, int index, set<int>& res, int sum) {//二叉树的方式进行遍历,此时所有的答案都在叶子节点
if (index > 10) { //表示当前的位置已经将数组全部遍历完了
if(sum>0)res.insert(sum);//到达叶子结点,将结果写入结果集
return;
}
//当进入左节点时,就是不选当前节点,就不加上结果就行了
dfs(f, index + 1, res, sum);
//当进入右节点,表示选择当前节点,就将当前 节点加入到sum中
sum += f[index];
dfs(f, index + 1, res, sum);
sum -= f[index];
}
int main() {
int f[10];
set<int> res;
for (int i = 0; i < 10; i++) {
f[i] = fac(i);
}
dfs(f, 0, res, 0);
//for (int i : res) cout << i << " ";
int n;
while (cin >> n) {
if (n < 0) return 0;
if (res.count(n)) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
算法3
(位运算) $O(2^n)$
C++ 代码
#include<iostream>
#include<set>
using namespace std;
int fac(int n) {
if (n == 0) return 1;
return n * fac(n - 1);
}
int main() {
int f[10];
set<int> res;
for (int i = 0; i < 10; i++) {
f[i] = fac(i);
}
for (int i = 0; i < (1 << 10); i++) {
int sum = 0;
for (int j = 0; j < 10; j++) {
if (i >> j & 1) {
sum += f[j];
}
}
if(sum>0)res.insert(sum);
}
//for (int i : res) cout << i << " ";
int n;
while (cin >> n) {
if (n < 0) return 0;
if (res.count(n)) cout << "YES" << endl;
else cout << "NO" << endl;
}
}