回溯法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
解题一般步骤：
（1）针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
（2）确定结点的扩展搜索规则
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

17. Letter Combinations of a Phone Number(Medium)

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
给定一串2-9的数字，返回其在手机按钮上可能的组合。
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

image.png

思路：经典的回溯组合问题，可以先把数字对应的字母序列做一个mapping字典，循环或递归加入每个字符，需要一个list保存当前正在加入的字符串。

循环的方法

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        mapping = {
            '2':'abc',
            '3':'def',
            '4':'ghi',
            '5':'jkl',
            '6':'mno',
            '7':'pqrs',
            '8':'tuv',
            '9':'wxyz'
        }
        result = [""]
        for d in digits:
            tmp = []
            for letter in mapping[d]:
                for res in result:
                    tmp.append(res + letter)
            result = tmp
        return result

递归的方法

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        d = {'2':"abc",
             '3':"def",
             '4':"ghi",
             '5':"jkl",
             '6':"mno",
             '7':"pqrs",
             '8':"tuv",
             '9':"wxyz"
            }
        res = []
        self.dfs(d, digits, "", res)
        return res
    
    def dfs(self, d, digits, tmp , res):
        if not digits:
            res.append(tmp)
        else:
            for num in d[digits[0]]:
                self.dfs(d, digits[1:], tmp + num, res)

---

22. Generate Parentheses(Medium)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
给的那个n对括号，写出所有配对括号的组合
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

思路：dfs回溯，设left，right来表示剩余括号数，每当出现一个括号就让left或right减一。

    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n < 1:
            return [""]
        res = []
        self.dfs(n ,n , res, "")
        return res
        
    def dfs(self, left, right, res, tmp):
        if left > right or left < 0 or right < 0:
            return 
        if left == 0 and right == 0:
            res.append(tmp)
        self.dfs(left - 1, right, res, tmp + '(')
        self.dfs(left , right - 1, res, tmp + ')')

---

39. Combination Sum(Medium)

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
给定一些被选中的数字（没有重复的）和一个目标数，找到满足在给定数字序列中和为目标数的集合。数字可以重复使用
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
所有的数都是正整数，不能包含重复的组合。
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

思路：该题数组没有排好序，首先得排序。剩下的同样，dfs递归的套路都差不多，用一个辅助函数，每遍历一个数就加入待定的数组tmp，再把目标书target 减去当前遍历过的数。

    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort()
        self.dfs(candidates, 0, target, res, [])
        return res
    
    def dfs(self, candidates, index, target, res, tmp):
        if target < 0:
            return 
        if target == 0:
            res.append(tmp)
            return 
        for i in range(index, len(candidates)):
            self.dfs(candidates, i, target - candidates[i] , res, tmp+[candidates[i]])

---

40. Combination Sum II(Medium)

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
给定一些被选中的数字和一个目标数，找到满足在给定数字序列中和为目标数的集合。每个数只能使用一次
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

思路：跟39题非常像，区别在于数组内的数不能重复使用，但数组内可以有重复的数，注意一下相同的数不要遍历两次产生重合的结果就好了

    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if not candidates:
            return []
        candidates.sort()
        res = []
        self.dfs(candidates, target, res, [])
        return res
    
    def dfs(self, candidates, target, res ,tmp):
        if target < 0:
            return 
        if target == 0:
            res.append(tmp)
            return 
        for i in range(len(candidates)):
            if i!=0 and candidates[i] == candidates[i-1]:
                continue
            self.dfs(candidates[i+1:], target-candidates[i], res, tmp+[candidates[i]])
        

---

46. Permutations(Medium)

Given a collection of distinct integers, return all possible permutations.
给定不同的整数的集合,返回所有可能的排列。
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

思路：O(n2)的方法，如果上面的题会了这道题就算简单题了，47题、77题、78题都是类似的。

    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(nums, res,[])
        return res 
    
    def dfs(self, nums, res,tmp):
        if not nums:
            res.append(tmp)
        else:
            for i in range(len(nums)):
                self.dfs(nums[:i]+nums[i+1:],res,tmp+[nums[i]])

---

79. Word Search（Medium）

Given a 2D board and a word, find if the word exists in the grid.
给定一个2维数组和一个单词，找到单词是否存在于2维数组中。
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false

思路：每次遍历到错误的节点需要返回，最完美的解决办法就是回溯了，从每个节点出发判断上下左右四个节点是不是匹配word的下一个字母，如果匹配则继续dfs递归，不匹配或者超过边界则返回。

    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not word: return True
        if not board: return False
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfs(board, i, j, word):
                    return True
        return False
    
    def dfs(self, board, i, j, word):
        if not word:
            return True
        if i >= len(board) or i < 0 or j >= len(board[0]) or j < 0 or board[i][j] != word[0]: #匹配失败跳出递归
            return False
        tmp = board[i][j]
        board[i][j] = '.'
        if self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) or \
        self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:]):
            return True
        board[i][j] = tmp
        return False

---