新集合
思路
由于 只有
，因此我们可以暴力枚举当前数是否被选即可。
时间复杂度
class Solution {
private:
int mp[21][21];
int vis[21];
int ans;
public:
/**
* 返回新集合的种类数
* @param n int整型 集合大小
* @param m int整型 限制数量
* @param limit Point类vector 不能同时出现的(u,v)集合
* @return int整型
*/
void dfs(int x, int n) {
if (x == n + 1) {
++ans;
return;
}
dfs(x + 1, n);
for (int i = x + 1; i <= n; ++i) vis[i] += mp[x][i];
if (!vis[x]) dfs(x + 1, n);
for (int i = x + 1; i <= n; ++i) vis[i] -= mp[x][i];
}
int solve(int n, int m, vector<Point>& limit) {
// write code here
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
mp[i][j] = 0;
vis[i] = 0;
}
ans = 0;
for (auto cur: limit) {
int u = cur.x, v = cur.y;
mp[u][v] = mp[v][u] = 1;
}
dfs(1, n);
return ans;
}
}; 
查看10道真题和解析
网易游戏公司福利 650人发布