用深搜求出子集,枚举每个自己中是否存在limit数组中的元素
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int 集合大小 * @param m int 限制数量 * @param limit Pointvector 不能同时出现的(u,v)集合 * @return int */ int cnt = 0; int vis[25] = { 0 }; void dfs(int k, int n, vector<Point>& limit) { if (k == n) { int flag = 1; for (int i = 0; i < limit.size(); i++) { if (vis[limit[i].x - 1] && vis[limit[i].y - 1]) { flag = 0; break; } } if (flag) cnt++; return; } vis[k] = 1; dfs(k + 1, n, limit); vis[k] = 0; dfs(k + 1, n, limit); } int solve(int n, int m, vector<Point>& limit) { dfs(0, n, limit); return cnt; } };