题解 | NC613 #新集合#

题目描述

集合 s 中有整数 1 到 n，牛牛想从中挑几个整数组成一个新的集合。
现在牛妹给牛牛加了 m 个限制，每个限制包含两个整数 u 和 v ，且 u 和 v 不能同时出现在新集合中。请问牛牛能组成的新集合多少种。可以选 0 个数。返回一个整数，即新集合的种类数。
示例1
输入：3,2,[(1,2),(2,3)]
返回值：5
说明：当 n = 3 时，共有 8 个子集，当加上限制 (1, 2), (2, 3) 后，合法的自己有 [], [1], [2], [3], [1, 3] 共 5 个

题目分析

对于n个不同的整数，它们能够组成的集合总数为2^n个，题目在此基础上增加了一些限制，基本的思路是将所有可能的情况记录下来，然后每种情况都做一次限制的判断，若满足则记录个数。如下图，对例题的集合分析。
图片说明

解题思路

方法1：使用数组记录使用过的数字，dfs遍历所有可能的情况，每个数字可以有选择和不选择两种情况，记录满足条件的情况数
1.因为n不超过20，所以可以定义一个长度为21的数组：boolean[] used = new boolean[21]; // boolean[i]表示i数字是否被加入集合中;
2.dfs的过程如下：

dfs(n, x, limit){
  if(n>x) return;
  // 选择x加入集合，used[x] = true;
  dfs(n, x+1, limit);
  // 不选择x加入集合，used[x] = false;
  dfs(n, x+1, limit);
}

方法2：使用一个数直接代替数字的集合，0~2^n刚好是数字的所有集合情况，对每种情况直接判断记录满足限制条件的集合
此方法与方法1思想类似，都是遍历所有的集合情况，不过这里直接用到了一个int变量 mask来表示集合情况（mask的二进制位置上是1的表明在集合中）,mask的取值范围是0~2^n；

代码实现

方法1：穷举递归所有可能的情况

    // 记录数字是否被使用过，数字最大为20
    boolean[] used = new boolean[21];
    int res = 0;
    public int solve (int n, int m, Point[] limit) {
        // write code here
        // 从1开始
        dfs(n, 1, limit);
        return res;
    }

    public void dfs(int n, int x, Point[] limit){
        if(x>n){
            // 说明集合选择完成，判断集合中的数字是否满足限制
            for(int i=0;i<limit.length;i++){
                if(used[limit[i].x] && used[limit[i].y]){
                    // 不满足条件直接返回
                    return;
                }
            }
            res++;
            return;
        }
        // 选择x
        used[x] = true;
        dfs(n, x+1, limit);
        // 不选择x
        used[x] = false;
        dfs(n, x+1, limit);
    }

时间复杂度： $O(2^n*m)$ ，所有的数字组合情况为2^n种，每种都要进行最多m的次限制条件判断，总共花费的时间为2^n*m；
空间复杂度： $O(n)$ ，集合最多有n个数字，递归深度为n；

方法2：使用数字代替穷举情况，直接对每种情况进行判断

    public int solve (int n, int m, Point[] limit) {
        // write code here
        int res = 0;
        for(int mask=0;mask<(1<<n);mask++){
            // mask 从0 到 2^n，可以表示成数字的所有集合
            boolean valid = true;
            for(Point point:limit){
                // 对于每个数字集合，需要判断是否满足条件
                if(isvalid(mask, point.x,point.y)){
                    valid = false;
                    break;
                }
            }
            // 当情况满足条件，则结果数加1
            if(valid){
                res++;
            }
        }
        return res;
    }

    public boolean isvalid(int mask, int u, int v){
        // 检验u和v是否同时出现在mask中（看mask中的u对应的位置是否是1）
        if(((mask>>(u-1))&1) == 1 && ((mask>>(v-1))&1) == 1){
            return true;
        }
        return false;
    }

时间复杂度： $O(2^n*m)$ ，所有的数字组合情况为2^n种，每种都要进行最多m的次限制条件判断，总共花费的时间为2^n*m；
空间复杂度： $O(1)$ ，只需要常数级别的变量空间；