用DFS（广度优先遍历）解决组合问题

从元素集中选取几个元素构成子集，求解可以构成子集的数目，与排列的主要区别是子集中元素顺序不同视为同一个子集

解题思路：

1. 解题时要注意进行剪枝处理，与排列问题解法的区别是对每次迭代要重新设置起始值，避免出现添加了之前的元素造成顺序不同的同一个子集被添加到答案中的情况。
2. 如果没有重复元素，不需要用数组对访问过的元素进行标记，因为剪枝过程可以避免访问到之前的添加过的元素。
3. 如果有重复元素，需要对原始数组进行排序，每次遍历元素需要标记，因为需要判断重复元素和第一个出现的元素是否同时出现在一个子集中，如果没有，这个重复元素可以跳过。

LeetCode上经典应用题目：
77 组合（没有重复元素）
输入：n = 4 ， k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> combinations = new ArrayList<>();
    List<Integer> combineList = new ArrayList<>();
    backtracking(combineList, combinations, 1, k, n);
    return combinations;
}

private void backtracking(List<Integer> combineList, List<List<Integer>> combinations, int start, int k, final int n) {
    if (k == 0) {
        combinations.add(new ArrayList<>(combineList));
        return;
    }
    for (int i = start; i <= n - k + 1; i++) {  // 剪枝
        combineList.add(i);
        backtracking(combineList, combinations, i + 1, k - 1, n);
        combineList.remove(combineList.size() - 1);
    }
}

90 含有相同元素求子集
输入：nums = [1,2,2]
输出：
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> subsets = new ArrayList<>();
    List<Integer> tempSubset = new ArrayList<>();
    boolean[] hasVisited = new boolean[nums.length];
    for (int size = 0; size <= nums.length; size++) {
        backtracking(0, tempSubset, subsets, hasVisited, size, nums); // 不同的子集大小
    }
    return subsets;
}

private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets, boolean[] hasVisited,
                          final int size, final int[] nums) {

    if (tempSubset.size() == size) {
        subsets.add(new ArrayList<>(tempSubset));
        return;
    }
    for (int i = start; i < nums.length; i++) {
        if (i != 0 && nums[i] == nums[i - 1] && !hasVisited[i - 1]) {
            continue;
        }
        tempSubset.add(nums[i]);
        hasVisited[i] = true;
        backtracking(i + 1, tempSubset, subsets, hasVisited, size, nums);
        hasVisited[i] = false;
        tempSubset.remove(tempSubset.size() - 1);
    }
}