新集合 牛客编程巅峰赛S1第11场 - 青铜&白银

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

回溯法

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;
    }
}

例子