【DFS】90.子集II

题目

法1：DFS

经典方法，必须掌握！！！

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums, 0, res, tmp);

        return res;
    }

    public void dfs(int[] nums, int startIndex, List<List<Integer>> res, List<Integer> tmp) {
        if (startIndex == nums.length) {
            res.add(new ArrayList<>(tmp));
            return;
        }

        tmp.add(nums[startIndex]); // 选择startIndex
        dfs(nums, startIndex + 1, res, tmp);
        tmp.remove(tmp.size() - 1); // 不选startIndex
        while (startIndex + 1 < nums.length && nums[startIndex + 1] == nums[startIndex]) { // 如果去掉这个条件，则可解决【78.子集】
            ++startIndex;
        }
        dfs(nums, startIndex + 1, res, tmp);
    }
}