1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        helper(ans, new ArrayList<>(), nums, 0);
        return ans;
    }

    private void helper(List<List<Integer>> ans, List<Integer> curr, int[] nums, int pos) {
        if (pos == nums.length) {
            ans.add(new ArrayList<>(curr));
            return;
        }
        for (int i = pos; i < nums.length; i++) {
            if (i > pos && nums[i - 1] == nums[i]) {
                continue;
            }
            curr.add(nums[i]);
            helper(ans, curr, nums, i + 1);
            curr.remove(curr.size() - 1);
        }
        ans.add(new ArrayList<>(curr));
    }
}

这个思路就是找一个数字来当开头. curr第0个位置, 我们从nums中从左到右分别找数字当开头. 比如开始是nums中第0个数字当开头, 然后继续, 我们得到剩下的nums的数字, 然后看curr第1个位置谁当开头, 一样从左到右开始轮流当开头. 一直到最后所有数字都当过开头后, 我们还有一种情况就是没有数字当开头, 也就是剩下的数字我都不选. 这也是第22行的效果.

15行的意思就是在决定curr当前位置谁当开头的时候, 如果之前当过的就别当了, 因为我们不允许有duplicates.

我们发现如果第10行这个if判断去掉, 我们到达pos == nums.length的时候, 不会进入for循环, 然后同样执行22行然后返回, 和我们现在写的逻辑一样, 因此我们可以把10行if去掉, 但这会让代码可读性降低.

这道题也可以理解给curr的每个位置放数字. 选择一个数字后, 后续的位置只能从该数字后面挑, 比如我们在curr的位置3放了nums[5],
那么位置4只能从5之后的数字里面挑, 因为为了避免重复

时间复杂度:O(2^n)因为nums中的数字可以出现和不出现两种情况.
空间复杂度:O(n)递归做多就是n层,也就是curr有n个位置都有数字.