LC 17 & LC 77 & LC 216

Solution to LeetCode 17 Letter Combinations of a Phone Number, LeetCode 77 Combinations, and LeetCode 216 Combination Sum III.

LeetCode 77

Combinations (Medium) [link]

1] Brute Force Solution for k=2:

for i in range(1,n+1):
      for j in range(i+1, n+1):
          print([i,j])

Brute Force Solution for k=3:

for i in range(1, n+1):
      for j in range(i+1, n+1):
          for u in range(j+1, n+1):
                  print([i,j,u])

The time complexity is O(n^k).

2] Recursion / Backtracking

n is the width of the recursion tree. k is the depth of the recursion tree.

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        path = []
        def backtrack(n, k, start):
            if len(path) == k:
                res.append(path[:])
                return
            for i in range(start, n + 1):
                path.append(i)
                backtrack(n, k, i+1)
                path.pop()    
        backtrack(n, k, 1)
        return res

3] Optimization by pruning the tree

Prune the tree: any recursion starting from the second element in current tree level is meaningless. len(path) is the number of element in the list at the current stage. k-len(path) is the number of additional elements we need. k-len(path)+1 is the starting point of recursion, at most. So to prune the tree, we end for loop at k-len(path)+1.

The time complexity is O(k* (n choose k)). It takes O((n choose k)) to enumerate combinations. And it takes O(k) to store each combination.

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        path = []
        def backtrack(n, k, start):
            if len(path) == k:
                res.append(path[:])
                return
            for i in range(start, n-(k-len(path))+1 +1):
                path.append(i)
                backtrack(n, k, i+1)
                path.pop()
        backtrack(n, k, 1)
        return res

LeetCode 216

Combination Sum III (Medium) [link]

We are going to find all combinations of length k that sum up to the target number n. The time complexity is O(k* (n choose k)).

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        path = []
        def backtrack(n, k, start):
            if len(path) == k:
                if sum(path) == n:
                    res.append(path[:])
                return
            for i in range(start, 9-(k-len(path))+2):
                path.append(i)
                backtrack(n, k, i+1)
                path.pop()
        backtrack(n, k, 1)
        return res

LeetCode 17

Letter Combinations of a Phone Number (Medium) [link]

Backtrack a string.

The time complexity is O(4^n), where 4 is the max number of characters represented by one number, n is the length of the input. Space complexity is O(4^n + n).

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []
        path = ""
        MAP = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        if not digits: return []
        
        def backtrack(digits, index, path):
            if len(digits) == len(path):
                res.append(path[:])
                return
            digit = int(digits[index])
            letters = MAP[digit]
            for i in range(len(letters)):
                path += letters[i]
                backtrack(digits, index+1, path)
                path = path[:-1]
        backtrack(digits, 0, path)
        return res