Combination-based DFS

Posted on | In
Summary of combination-based DFS.

Combination-based DFS

subsets

Given a set of distinct integers, return all possible subsets.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def subsets(self, nums):
        nums = sorted(nums) # only sort if we need output of ascending order
        combinations = []
        self.dfs(nums, 0, [], combinations)
        return combinations
    
    def dfs(self, nums, index, combination, combinations):
        combinations.append(list(combination))

        for i in range(index, len(nums)):
            combination.append(nums[i])
            self.dfs(nums, i+1, combination, combinations)
            combination.pop() # backtracking

The DFS will build a tree with each node representing a subset.

e.g. [1,2,3]

1
2
3
4
5
6
7
          []
      /   |   \
   [1]   [2]  [3]
  /  \     \
[1,2] [1,3] [2,3]
  |
[1,2,3]

follow-up: what if nums contain duplicate numbers?

Then we must sort nums, and add a condition in dfs, that is when the next number is the same as previous one, we need skip the next dfs since we don’t want pass the same current combination to the next dfs, otherwise, this would cause duplicate subsets where nums are the same but in different order.