算法练习Day21 （Leetcode/Python-回溯算法）

216. Combination Sum III

Find all valid combinations of?k?numbers that sum up to?n?such that the following conditions are true:

• Only numbers?1?through?9?are used.
• Each number is used?at most once.

Return?a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

思路：和昨天的那题很相似，不过结束条件不太一样。以及在回溯的时候需要多记录一个值。

class Solution(object):
    def backtrack(self, target, k, currentSum, startIndex, path, result):
        if currentSum > target: # early stop
            return
        if len(path) == k: # 判断是否满足条件
            if currentSum == target:
                result.append(path[:])
            return 
        for i in range(startIndex, 9-(k-len(path)) + 2): # 如果已经有两个元素，而总共需要5个，那么9-（5-2）+ 2 = 8，最后一个值取不到，所以有7个值可取。
            currentSum += i 
            path.append(i)
            self.backtrack(target, k, currentSum, i+1, path, result) # 注意这里是i不是startIndex
            path.pop()
            currentSum -= i

    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        result = []
        self.backtrack(n,k,0,1,[],result)
        return result 

17. Letter Combinations of a Phone Number

这里一个数字对应三个字母，所以相当于二叉树变得更宽了（每一层有更多的子节点）。另外注意，这里用来记录每条“路径”的是string，所以不能用pop()来回溯，而要用[:-1]

class Solution(object):
    def __init__(self):
        self.letterMap = [
            "", #0 
            "", #
            "abc",
            "def",
            "ghi",
            "jkl",  # 5
            "mno",  # 6
            "pqrs", # 7
            "tuv",  # 8
            "wxyz"  # 9
        ]
        self.result = []
        self.s = ""

    def backtrack(self, digits, index):
        if index == len(digits):
            self.result.append(self.s)
            return 
        digit = int(digits[index])
        letters = self.letterMap[digit]
        for i in range(len(letters)):
            self.s += letters[i]
            self.backtrack(digits, index+1)
            self.s = self.s[:-1] # this is a string, so the pop() cannot be used 


    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if len(digits) == 0:
            return self.result
        self.backtrack(digits, 0)
        return self.result