90. Subsets II

https://leetcode.com/problems/subsets-ii/

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Thoughts

对给定数组返回它的powerset。找所有=>DFS。DFS每步从剩下的元素中选择一个元素。设置当前选择范围的起始位置以避免重复选择之前的元素。Input有重复的数字，要求输出subset不重复。[1, 2, 2]，在[1]时选第二个2由于和选第一个2时产生的结果相同，要跳过DFS同一层的其它相同元素。不同层之间相同元素没影响。为了方便跳过相同元素，排序。

Code

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        def dfs(pos, res, path):
            for i in range(pos, len(nums)):
                if i == pos or nums[i] != nums[i - 1]:
                    path.append(nums[i])
                    dfs(i + 1, res, path)
                    path.pop()
            res.append([i for i in path])
        dfs(0, res, [])
        return res

class Solution {
    private void helper(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));

        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            helper(nums, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

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

Analysis

最差是没有重复的数, 依然O(N^2).