题意整理

• 给定一个集合包含1到n共n个数，从中选若干数出来组成新的集合。
• 规定一个限制数组，限制数组里的每一个数对不能同时出现在新集合中。
• 求这样的新集合有多少个。

方法一（二进制枚举）

1.解题思路

• 定义1个mask，表示1到n有没有出现过，若mask最低位为1，则表示1出现过，次低位为1，则表示2出现过。比如$mask=101mask=101$mask=101时，表示出现了1和3，对应集合$[1,3][1,3]$[1,3]。
• 根据二进制位可以很容易判断某个数有没有出现过，从而枚举二进制位的时候，根据限制数组，看里面的数对是否同时出现过，如果同时出现，则当前集合不合法。
• 如果没有同时出现，则计数加一。

动图展示：

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 集合大小
     * @param m int 限制数量
     * @param limit Point一维数组 不能同时出现的(u,v)集合
     * @return int
     */
    public int solve (int n, int m, Point[] limit) {
        //定义结果变量
        int res=0;
        
        //遍历mask
        for(int mask=0;mask<(1<<n);mask++){
            //判断当前集合是否可行
            boolean pass=true;
            for(Point point:limit){
                //如果u、v同时出现，则排除
                if(check(mask,point.x,point.y)){
                    pass=false;
                    break;
                }
            }
            if(pass){
                res++;
            }
        }
        return res;
    }
    
    //通过mask校验u和v有没有同时出现
    private boolean check(int mask,int u,int v){
        if(((mask>>(u-1))&1)==1&&((mask>>(v-1))&1)==1){
            return true;
        }
        return false;
    }
}

3.复杂度分析

• 时间复杂度：二进制mask总共有$2^{n}2^n$2n个，对于每个mask都需要检查u、v是否同时出现，检查u、v是否同时出现的时间复杂度是O(m)，所以时间复杂度为$O(m\ast 2^n)O(m*2^n)$O(m∗2n)。
• 空间复杂度：不需要额外的空间，所以空间复杂度为$O\left(1\right)O(1)$O(1)。

方法二（递归）

1.解题思路

• 根据限制数组，建立图的邻接矩阵。
• 然后通过递归的方式枚举所有的集合。
• 如果之前出现的某个数和当前数同时出现在图中，则不可行，直接返回。否则列出所有可行的集合，每列出一个可行集合，计数加一。

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 集合大小
     * @param m int 限制数量
     * @param limit Point一维数组 不能同时出现的(u,v)集合
     * @return int
     */
    //整数数目
    int n;
    //对限制数组建图
    int[][] graph;
    //标记数组
    boolean[] v;
    //结果变量
    int res;
    public int solve (int n, int m, Point[] limit) {
        //初始化
        this.n=n;
        this.graph=new int[n+1][n+1];
        this.v=new boolean[n+1];
        this.res=0;
        
        //建图
        for(Point point:limit){
            graph[point.x][point.y]=1;
            graph[point.y][point.x]=1;
        }
        //递归
        dfs(1);
        return res;
    }
    
    //递归
    private void dfs(int i){
        if(i>n){
            res++;
            return;
        }
        dfs(i+1);
        //如果同时出现，直接返回
        for(int j=1;j<i;j++){
            if(v[j]&&graph[i][j]==1){
                return;
            }
        }
        //回溯，看1到n之间的某个数有没有出现过
        v[i]=true;
        dfs(i+1);
        v[i]=false;
    }
}

3.复杂度分析

• 时间复杂度：递归的深度为n，每层递归里面都要检查u、v是否同时出现，所以时间复杂度为$O(n\ast 2^n)O(n*2^n)$O(n∗2n)。
• 空间复杂度：需要额外大小为n的递归栈、大小为$n+1n+1$n+1的标记数组以及大小为${(n+1)}^2\{(n+1)\}^2$(n+1)2的邻接矩阵，所以空间复杂度为$O\left(n^2\right)O(n^2)$O(n2)。