90. Subsets II

Information

  • Diffculty: Medium

  • Created: 2020-03-11 07:44:00

  • Last Motified: 2020-03-11 07:49:37

  • Tags: Array, 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()