DFS

Subsets

leetcode

Approach: use array index start to keep track of visited, i.e., nums[:start] are visited, nums[start:] are not.

class Solution():
 
    def __init__(self):
        self.ans = []
 
    def dfs(self, nums, stack: list, start: int):
        self.ans.append(stack)
        if start >= len(nums):
            return
 
        for i in range(start, len(nums)):
            stack.append(nums[i])
            self.dfs(nums, stack[:], i+1)
            stack.pop()
 
    def subset(self, nums):
        self.dfs(nums, [], 0)
 
        return self.ans

Subsets II

leetcode

Approach: The array may contain duplicates, and the solution set must not contain duplicate subsets.

Tip

Duplicate subsets are not allowed but duplicate elements in the same subset is. So any subset cannot appear more than once, but subset like [1,2,2] is allowed.

class Solution():
 
    def __init__(self):
        self.ans = []
 
    def dfs(self, nums, stack: list, start: int):
        self.ans.append(stack)
        if start >= len(nums):
            return
 
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            stack.append(nums[i])
            self.dfs(nums, stack[:], i+1)
            stack.pop()
 
    def subset(self, nums):
        self.dfs(nums, [], 0)
 
        return self.ans

One of my mistakes was:

for i in range(start, len(nums)):
-    if i > 0 and nums[i] == nums[i-1]:
+    if i > start and nums[i] == nums[i-1]:
        continue
    stack.append(nums[i])
    self.dfs(nums, stack[:], i+1)
    stack.pop()

This yields wrong answer [[], [1], [1, 2], [2]].