现在牛妹给牛牛加了 个限制 ,每个限制包含两个整数 和 ( ),且 和 不能同时出现在新集合中 。
请问牛牛能组成的新集合多少种。
可以选 0 个数。
返回一个整数,即新集合的种类数。
现在牛妹给牛牛加了 个限制 ,每个限制包含两个整数 和 ( ),且 和 不能同时出现在新集合中 。
请问牛牛能组成的新集合多少种。
可以选 0 个数。
返回一个整数,即新集合的种类数。
3,2,[(1,2),(2,3)]
5
当 n = 3 时,共有 8 个子集,当加上限制 (1, 2), (2, 3) 后,合法的自己有 [], [1], [2], [3], [1, 3] 共 5 个
第一个参数为 。
第二个参数为 。
第三个参数为 对 (u, v) 。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int 集合大小 * @param m int 限制数量 * @param limit Pointvector 不能同时出现的(u,v)集合 * @return int */ int solve(int n, int m, vector<Point>& limit) { vector<int> nums(n); iota(begin(nums), end(nums), 1); vector<int> candidates; vector<vector<int>> subsets; function<void(int)> backtracking = [&](int p) { subsets.emplace_back(candidates); for (int i = p; i < n; ++i) { candidates.emplace_back(nums[i]); backtracking(i + 1); candidates.pop_back(); } }; backtracking(0); int ans = 0; for (const auto& subset : subsets) { if (subset.size() < 2) { // 空集或只有一个元素的集合肯定满足条件 ++ans; continue; } bool flag = true; for (const auto& l : limit) { if (find(begin(subset), end(subset), l.x) != end(subset) && find(begin(subset), end(subset), l.y) != end(subset)) { flag = false; // 同时出现u, v break; } } ans += flag; } return ans; } };
static bool judge(int num,int u,int v) { int val1=(num>>(u-1)&1); int val2=(num>>(v-1)&1); //对应位上的数字 if(val1==1 && val2==1) return false; else return true; } int solve(int n, int m, vector<Point>& limit) { // write code here int count=0; for(int val=0;val<=((1<<n)-1);val++) //val为0=> 2的n次方-1 { bool flag=true; for(auto item:limit) { if(judge(val,item.x, item.y)==false) //不满足互斥性 { flag=false; break; } } if(flag) count++; } return count; }