暴力出所有的可能集合，再与要求的限制作比较。最终求出能组成的新集合数量。

有n个元素,每个元素都有取与不取的两种可能,所以应该是2^n个.

因为n<=20，故至多有10^6个集合，我们可以采用暴力搜索。

因为要遍历出所有的取值情况，我们使用回溯来解决此类问题。回溯类型的题目有一套通用的模板。

回溯法 

result = []
dfs backtrack(路径，选择列表):
    if(满足结束条件):
        result.add(路径)
        return
        做选择
        backtrack(路径，选择列表)
        撤销选择
        backtrack(路径，选择列表)

参考代码 

import java.util.*;
/*
 * public class Point {
 *   int x;
 *   int y;
 * }
 */
public class Solution {
    /**
     * 返回新集合的种类数
     * @param n int整型 集合大小
     * @param m int整型 限制数量
     * @param limit Point类一维数组 不能同时出现的(u,v)集合
     * @return int整型
     */
    int res = 0;
    boolean[] v;
    public void dfs(Point[] limit,int x,int n){
        if(x>n){
            for(Point lim : limit)
                if(v[lim.x]&& v[lim.y]) return;
            res++;
            return;
        }
        v[x] = true;
        dfs(limit,x+1,n);
        v[x] = false;
        dfs(limit,x+1,n);
    }
    public int solve(int n, int m, Point[] limit){
        v = new boolean[n+1];
        dfs(limit,1,n);
        return res;
    }
}

例子


例子