题意：

给你一个 $1\sim n$ 的整数集合，再给你 $m$ 个限制条件，条件的形式如下：

第 $i$ 个条件给你两个数 $u,v$ ，表示 $u$ 和 $v$ 不能在同一个集合中

现在问你总共有多少种选法，使得所选集合满足条件？

解法一（暴力枚举）

发现本题中数据范围 $n<=20$ ，于是我们可以直接枚举每一个数字选或者不选两种情况，最后枚举完所有情况后再判断是否满足条件即可

具体的：

我们定义递归函数 $dfs(k)$ 表示当前考虑到第 $k$ 个数字，然后枚举两种情况继续递归即可，到递归边界 $k>n$ 再进行判断是否满足条件

递归树如下图：

代码：

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */

class Solution {
public:
    vector<Point> limit;
    int n,m;
    bool use[21];
    int ans;
    void dfs(int k){//考虑第k个数字
        if(k>n){
            //n个数字已经全部决策完毕
            for(int i=0;i<m;i++){
                int u=limit[i].x,v=limit[i].y;
                //两个数在同一个集合中
                if(use[u]&&use[v])return;
            }
            ans++;
            return;
        }
        //选择当前数字
        use[k]=true;
        dfs(k+1);
        //不选择当前数字
        use[k]=false;
        dfs(k+1);
    }
    int solve(int n, int m, vector<Point>& limit) {
        this->n=n,this->m=m,this->limit=limit;
        ans=0;
        memset(use,0,sizeof use);//多测清空
        //从第一个数字开始考虑
        dfs(1);
        return ans;
    }
};

时间复杂度： $O(2^n*m)$ ，每个数字有两种方案，有 $n$ 个数字，故总共有 $2^n$ 种方案，故枚举方案数的时间代价是 $O(2^n)$ ，枚举每一种方案需要判断是否满足条件，代价是 $O(m)$ 的，故总的时间复杂度是 $O(2^n*m)$

空间复杂度： $O(n+m)$ ，总共有 $n$ 个数字，递归深度是 $O(n)$ 的，再加上存储限制条件需要 $O(m)$ 的空间，故总的空间复杂度为 $O(n+m)$

解法二（状态压缩优化判断）

我们考虑优化解法一中判断所选集合是否满足条件的过程

我们可以用一个二进制整数 $state[i]$ 表示若数字 $i$ 在集合中，则哪些数字不能在集合中

具体的：

若这个二进制整数第 $k$ 位为1，则若数字 $i$ 在集合中，数字 $k$ 就不能在集合中

我们预处理上述 $state$ 数组只需要枚举所有限制条件，然后对于第 $i$ 个限制条件，按位或运算即可

接下来我们可以定义递归函数 $dfs(k,now)$ 表示当前考虑第 $k$ 个数字，当前已选数字集合的二进制数表示为 $now$

那么，判断当前第 $k$ 个数字是否可以放到集合中可以用按位与运算在 $O(1)$ 的时间内解决

具体的：

若 $state[k]\& now$ 为0，则当前第 $k$ 个数字可以放入集合中，否则就不行

代码：

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */

class Solution {
public:
    int state[21];
    int n;
    int ans;
    void dfs(int k,int now){
        //当前考虑第k个数字，已选集合为now
        if(k>n){
            ans++;
            return;
        }
        if((now&state[k])==0){//可以放入
            dfs(k+1,now|(1<<k));
        }
        //不放入
        dfs(k+1,now);
    }
    int solve(int n, int m, vector<Point>& limit) {
        this->n=n;
        ans=0;
        memset(state,0,sizeof state);
        for(int i=0;i<limit.size();i++){
            int u=limit[i].x,v=limit[i].y;
            state[u]|=1<<v;
            state[v]|=1<<u;
            //预处理state数组
        }
        //从第一个数字开始考虑，刚开始一个数字也没有，集合表示为0
        dfs(1,0);
        return ans;
    }
};

时间复杂度： $O(2^n)$ ，总共有 $2^n$ 个方案，枚举方案数的时间代价是 $O(2^n)$ ，递归函数内的时间代价是 $O(1)$ ，故总的时间复杂度是 $O(2^n)$

空间复杂度： $O(n+m)$ ，总共有 $n$ 个数字，递归深度是 $O(n)$ 的，再加上存储限制条件需要 $O(m)$ 的空间，故总的空间复杂度为 $O(n+m)$

题解 | #新集合#

题意：

解法一（暴力枚举）

解法二（状态压缩优化判断）