Depth First Search

Catalogue

1. 1. Basic
2. 2. Subset
   1. 2.1. 78. Subsets
      1. 2.1.1. Sol1. Exist or not
      2. 2.1.2. Sol2. Position
      3. 2.1.3. Sol3. Iteration
   2. 2.2. 90. Subsets II
      1. 2.2.1. Sol1. 2 Branching
      2. 2.2.2. Sol2. Position
3. 3. Permutation
   1. 3.1. 46. Permutations
   2. 3.2. 47. Permutations II
   3. 3.3. 22. Generate Parentheses

Basic

We use DFS a lot in Tree or Graph.

• DFS can only be implemented by using recursion?

1. No. It can be implemented by using either iterative way, or in a recursive way.
2. it is easier to use recursion to implement. (pre,in,post order traversal iteration in tree)

• Method

1. What dose it store on each level?
2. How many different states should we try to put on the level?

Subset

O(2^n)

78. Subsets

Different recursion ways with different recursion Tree!

Sol1. Exist or not

Each node has two braching subtree!

# Time : O(2^n)
class Solution(object):
    def subsets(self, nums):
        if not nums: return []

        res = []
        self.dfs(nums, 0, [], res)
        return res

    def dfs(self, nums, idx, path, res):
        if idx == len(nums):
            res.append(path)
            return

        # Other programming language, we have to append,than pop in the path
        # But in python, we just add it as parameter!
        self.dfs(nums, idx + 1, path + [nums[idx]], res)
        self.dfs(nums, idx + 1, path, res)

Sol2. Position

Each level nodes have different number subtree

# Time : Hard to Analyze!
class Solution(object):
    def subsets(self, nums):
        if not nums: return []

        res = []
        self.dfs(nums, 0, [], res)
        return res

    def dfs(self, nums, idx, path, res):
        res.append(path)

        for i in xrange(idx, len(nums)):
            self.dfs(nums, i+1, path+[nums[i]], res)

Sol3. Iteration

class Solution(object):
    def subsets(self, nums):
        res = [[]]
        for num in nums:
            res += [item+[num] for item in res]
        return res

90. Subsets II

Sol1. 2 Branching

class Solution(object):
    def subsetsWithDup(self, nums):
        res = []
        nums.sort()
        self.dfs(nums, 0, [], res)
        return res


    def dfs(self, nums, idx, path, res):
        if idx == len(nums):
            res.append(path)
            return

        self.dfs(nums, idx + 1, path + [nums[idx]], res)

        while idx < len(nums)-1 and nums[idx] == nums[idx+1]:
            idx += 1

        self.dfs(nums, idx + 1, path, res)

class Solution(object):
    def subsetsWithDup(self, nums):
        nums.sort()
        pairs = []
        for num in nums:
            if not pairs or num != pairs[-1][0]:
                pairs.append([num, 1])
            else:
                pairs[-1][1] += 1
        self.res = []
        self.dfs(pairs, 0, [])
        return self.res

    def dfs(self, pairs, idx, path):
        if idx == len(pairs):
            self.res.append(path)
            return

        num, cnt = pairs[idx]
        for k in range(cnt+1):
            self.dfs(pairs, idx+1, path + ([num] * k))

Sol2. Position

• Position recursion can remove duplicates by removing same brachings!

class Solution(object):
    def subsetsWithDup(self, nums):
        if not nums:
            return []
        res = []
        self.dfs(sorted(nums), 0, [], res)
        return res

    def dfs(self, nums, idx, path, res):
        res.append(path)

        for i in xrange(idx, len(nums)):
            if i > idx and nums[i] == nums[i-1]:
                continue
            self.dfs(nums, i+1, path+[nums[i]], res)

    # Why we can not just append and pop new elements?
    # we should deep copy the results!!!
    def dfs1(self, nums, idx, path, res):
        res.append(copy.deepcopy(path))

        for i in xrange(idx, len(nums)):
            if i > idx and nums[i] == nums[i-1]:
                continue

            path.append(nums[i]) # python not suggested this way!
            self.dfs1(nums, i+1, path, res)
            path.pop()

Permutation

O(n!)

46. Permutations

class Solution(object):
    def permute(self, nums):
        res = []
        self.dfs(res, nums, [])
        return res

    def dfs(self, res, nums, path):
        if not nums:
            res.append(path)

        for i in xrange(len(nums)):
            self.dfs(res, nums[:i]+nums[i+1:], path+[nums[i]])

• TODO : Space Consuming

47. Permutations II

class Solution(object):
    def permuteUnique(self, nums):
        res = []
        self.dfs(sorted(nums), res, [])
        return res

    def dfs(self, nums, res, path):
        if not nums:
            res.append(path)
            return

        for i in xrange(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[:i]+nums[i+1:], res, path+[nums[i]])

22. Generate Parentheses

class Solution(object):
    def generateParenthesis(self, n):
        self.res = []
        self.dfs( n, n, [])
        return self.res

    def dfs(self, left, right, path):
        if left == right == 0:
            self.res.append(''.join(path))
            return

        if left > 0:
            self.dfs(left - 1, right, path + ['('])

        if right > left:
            self.dfs(left, right - 1, path + [')'])