基础算法——生成子集与集合运算¶
参考链接:https://blog.csdn.net/u011815404/article/details/98755754
https://blog.csdn.net/u011815404/article/details/98850980
与生成子集相呼应的是全排列,其实可以看成是生成子集的一种特殊问题,但是因为涉及题目较多,所以将全排列单独总结。
给定一个集合{0,1,2,3,...,n-1}
,生成所有的子集。
在刘汝佳的《算法竞赛入门经典》的7.2节完整的三种方法。
增量构造法¶
增量构造的思路是假定现在有{0,1,2,3,...,n-1}
个元素,首先肯定是空集,然后放入第一个元素0,然后将包含0的长度为1,2,3,...,n集合生成,然后用1替换掉0,按照上述规律继续生成长度为1,2,...,n-1的子集。这里cur
代表当前生成子集的长度,用数组A
去记录当长度为cur
时最后一个元素是多少,然后从该元素的下一个来进行构造。如果是自定义的集合,比如LeetCode的78,那就需要增加一个数组v
来保存结果,用A
记录下标。
//LeetCode 78
class Solution {
vector<vector<int>> res;
vector<int> v;
vector<int> A;
public:
vector<vector<int>> subsets(vector<int>& nums) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n = nums.size();
v.resize(n);
A.resize(n);
subset(0, n, nums);
return res;
}
void subset(int cur, int n, vector<int> & num)
{
vector<int> tmp(v.begin(), v.begin() + cur);
res.push_back(tmp);
int pos = cur ? A[cur - 1] + 1 : 0;
for (int i = pos; i < n; ++i) {
A[cur] = i;
v[cur] = num[i];
subset(cur + 1, n, num);
}
}
};
位向量法¶
位向量法思路和DFS很接近也非常好理解,用一个数组used
来记录当前元素是否被使用过,然后做DFS,比较推荐此方法,就不用去额外写一个数组A
去记录下标了。
//LeetCode 78
class Solution {
vector<vector<int>> res;
vector<bool> used;
public:
vector<vector<int>> subsets(vector<int>& nums) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n = nums.size();
used.resize(n, false);
subset(0, n, nums);
return res;
}
void subset(int cur, int n, vector<int> & nums)
{
if (cur == n) {
vector<int> tmp;
for (int i = 0; i < n; ++i) {
if (used[i]) tmp.push_back(nums[i]);
}
res.push_back(tmp);
return;
}
used[cur] = true;
subset(cur + 1, n, nums);
used[cur] = false;
subset(cur + 1, n, nums);
}
};
二进制法¶
利用标准库里的bitset
,包含在头文件bitset
里面,用法可以参考:https://blog.csdn.net/u011815404/article/details/90717924
固定长度的子集的生成¶
典型如LeetCode 77,n个数,生成长度为k的子集,如果是自定义子集,只需要在每次将元素推入tmp
的时候修改成下标对应的自定义的数组即可。
class Solution {
vector<int> tmp;
vector<vector<int>> res;
public:
vector<vector<int>> combine(int n, int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
DFS(n, k, 1);
return res;
}
void DFS(int n, int k, int level)
{
if (tmp.size() == k) {
res.push_back(tmp);
return;
}
for (int i = level; i <= n; ++i) {
tmp.push_back(i);
DFS(n, k, i + 1);
tmp.pop_back();
}
}
};
典型题目:
- LeetCode 78 Subset
- POJ 3977 subset
- POJ 2718