Subsets II

Problem Id: 90 Difficulty: Medium Tag: Array Tag: Backtracking


Intuition

We could use DFS to find all non-duplicate subsets.

Notice that, if a child is the same as previous visited child, we should skip it to avoid duplicate.

Solution


class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        path = []
        self._dfs(0, nums, path, ans)
        return ans

    def _dfs(self, start, nums, path, ans):
        ans.append(path[:])
        prev = None
        for i in range(start, len(nums)):
            child = nums[i]
            if child == prev:
                continue
            prev = child
            path.append(child)
            self._dfs(i + 1, nums, path, ans)
            path.pop()