题意

在1~n这$nn$n个数中选定几个数组成一个集合，使所有选出来的数都满足m个限制，求合法集合个数。

100分做法：暴力枚举

我们只需要将所有可能出现的数字集合都枚举出来，一一判断选出的数能否满足限制并计算个数即可。

代码如下

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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 集合大小
     * @param m int 限制数量
     * @param limit Pointvector 不能同时出现的(u,v)集合
     * @return int
     */
    vector<Point> Limit;
    int N,M;
    int ans=0,isUsed[30]={0};
    bool isValid()
    {
        bool flag=true;
        for(int i=0;i<M;i++) flag&=!(isUsed[Limit[i].x]&&isUsed[Limit[i].y]);//判断方案是否可行
        return flag;
    }
    void search(int now)
    {
        if(now>N)
            if(isValid()) {ans++;return;} else return;//若方案可行答案加一
        isUsed[now]=true;
        search(now+1);//选取now+1分支
        isUsed[now]=false;
        search(now+1);//不选取now+1分支
    }
    int solve(int n, int m, vector<Point>& limit) {
        // write code here
        N=n,M=m,Limit=limit;
        search(1);
        return ans;
    }
};

时间复杂度：$O\left(m{2}^n\right)O(m2^n)$O(m2n)，显然有$2^{n}2^n$2n个选择方法，每次调用$isValidisValid$isValid耗费时间为$mm$m，故时间复杂度为$O\left(m{2}^n\right)O(m2^n)$O(m2n)。 空间复杂度：$O\left(n\right)O(n)$O(n)，在递归中最多使用了$O\left(n\right)O(n)$O(n)的栈空间。

100分做法：优化枚举，剪枝

我们发现当有一个限制不满足时，整个集合一定不满足，故可以使用可行性剪枝优化。 将限制判断提前，防止不可行的搜索树展开，能节省大量时间复杂度。

例如，对于某个可能的答案集合A，若A中已经有两个数字u,v不能共存，那无论之后加的数字是什么，A一定都不是满足条件的集合，提前判断A中是否有互斥的数字，可以减少搜索量，防止搜索已经不可行的集合。

代码如下

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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 集合大小
     * @param m int 限制数量
     * @param limit Pointvector 不能同时出现的(u,v)集合
     * @return int
     */
    vector<Point> Limit;
    int N,M;
    int ans=0,isUsed[30]={0};
    bool isValid()
    {
        for(int i=0;i<M;i++)if(isUsed[Limit[i].x]&&isUsed[Limit[i].y])return false; return true;//判断方案是否可行，只要不行立刻返回，减除该搜索树
    }
    void search(int now)
    {
        if(now>N)
            if(isValid()) {ans++;return;} else return;//若方案可行答案加一
        isUsed[now]=true;
        search(now+1);//选取now+1分支
        isUsed[now]=false;
        search(now+1);//不选取now+1分支
    }
    int solve(int n, int m, vector<Point>& limit) {
        // write code here
        N=n,M=m,Limit=limit;
        search(1);
        return ans;
    }
};

时间复杂度：$O\left(2^n\right)O(2^n)$O(2n)，显然有$2^{n}2^n$2n个选择方法，每次调用$isValidisValid$isValid耗费时间为较小的常数$TT$T，故时间复杂度为$O\left(2^n\right)O(2^n)$O(2n)。 空间复杂度：$O\left(n\right)O(n)$O(n)，在递归中最多使用了$O\left(n\right)O(n)$O(n)的栈空间。

图片为n=5,m=6的一种情况，先从空集开始，逐步添加数字，若不满足限制就返回，直到所有的可行集合都被找到。