DFS组合类

dfs构建的过程中，思考的方式：递归的那一行不需要往下去思考，就直接考虑到递归出口的效果即可当做这一行执行完了，然后继续往下考虑。

回溯的时候，i这些整数，不需要进行回溯，因为整数这些基本类型是深拷贝的，只有数组对象这些东西，需要回溯，因为他们是引用传递的，其实也可以通过深拷贝来代替回溯

本问题下：深度优先搜索是一种更加灵活的方式，可以不知道循环的层数

所有子集

实现一，实现subset所有子集的方法

是0-1法，只有搜索树的叶子是所需要的结果

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return results;
    }
    Arrays.sort(nums);
    dfs(nums, 0, new ArrayLisy<Integer>(), results);
    return results;
}

// 1. 递归的定义
public void dfs(
	int[] nums,
    int index,
    List<Integer> subset,
    List<List<Integer>> results
) {
    // 3. 递归的出口
    if (index == nums.length) {
        // 深拷贝
        results.add(new ArrayList<Integer>(result));
        return;
    }
    // 2. 递归的拆解
    // 选 nums[index]
    subset.add(nums[index]);
    dfs(nums, i + 1, subset, result);
    subset.remove(subset.size() - 1);
    dfs(nums, i + 1, subset, result);
}

实现二，通用性更强，每一个节点都是结果（和全排列的代码也很像）

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return results;
    }
    Arrays.sort(nums);
    dfs(nums, 0, new ArrayLisy<Integer>(), results);
    return results;
}

// 1. 递归的定义
public void dfs(
	int[] nums,
    int startIndex,
    List<Integer> subset,
    List<List<Integer>> results
) {
    results.add(new ArrayList<Integer>(subset));
	
    // 2. 递归的拆解，结合这个循环的终止条件也作为递归的出口
    for (int i = startIndex; i < nums.length; i++) {
        subset.add(nums[i]);
        dfs(nums, i + 1, subset, result);
        subset.remove(subset.size() - 1);
    }
}

带重复元素的子集

去重：选代表

1. 单个数的时候，指针按序往下挪就可以
2. 多个数的时候，选代表就选，比如说2 2 2 2，只选前面紧挨着的2

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return results;
    }
    Arrays.sort(nums);
    dfs(nums, 0, new ArrayList<Integer>(), results);
    return results;
}

// 1. 递归的定义
public void dfs(
	int[] nums,
    int startIndex,
    List<Integer> subset,
    List<List<Integer>> results
) {
    results.add(new ArrayList<Integer>(subset));
	
    // 2. 递归的拆解，结合这个循环的终止条件也作为递归的出口
    for (int i = startIndex; i < nums.length; i++) {
        if (i != 0 && nums[i] == nums[i - 1] && i > startIndex) {
            continue;
        }
        subset.add(nums[i]);
        dfs(nums, i + 1, subset, result);
        subset.remove(subset.size() - 1);
    }
}