LC.P90[子集II]

方法一：排序+哈希表+回溯

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 {
    List<Integer> path = new ArrayList<>();
    Set<List<Integer>> ans = new HashSet<>();
    int[] nums;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        dfs(0);
        return new ArrayList<>(ans);
    }

    private void dfs(int i) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        dfs(i + 1); // 不选

        path.add(nums[i]); // 选
        dfs(i + 1);
        path.remove(path.size() - 1);
    }
}
  • 时间复杂度：$O(n2^n)$
  • 空间复杂度：$O(n)$

方法二：排序+回溯(选或不选)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    int[] nums;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        dfs(false, 0);
        return new ArrayList<>(ans);
    }

    /**
     * @param flag 是否选择前一个数
     * @param i    当前下标
     */
    private void dfs(boolean flag, int i) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // 不选
        dfs(false, i + 1);

        // 选
        if (!flag && i > 0 && nums[i - 1] == nums[i]) return;
        path.add(nums[i]);
        dfs(true, i + 1);
        path.remove(path.size() - 1);
    }
}
  • 时间复杂度：$O(n2^n)$
  • 空间复杂度：$O(n)$