算法思想
回溯实际上是一种试探算法，这种算法跟暴力搜索最大的不同在于，在回溯算法里，是一步一步地小心翼翼地进行向前试探，会对每一步探测到的情况进行评估，如果当前的情况已经无法满足要求，那么就没有必要继续进行下去，也就是说，它可以帮助我们避免走很多的弯路。
回溯算法的特点在于，当出现非法的情况时，算法可以回退到之前的情景，可以是返回一步，有时候甚至可以返回多步，然后再去尝试别的路径和办法。这也就意味着，想要采用回溯算法，就必须保证，每次都有多种尝试的可能。

解题步骤
判断当前情况是否非法，如果非法就立即返回；

当前情况是否已经满足递归结束条件，如果是就将当前结果保存起来并返回；

当前情况下，遍历所有可能出现的情况并进行下一步的尝试；

递归完毕后，立即回溯，回溯的方法就是取消前一步进行的尝试。
例题：

Leetcode39：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
画图
假设candidates=[2,3,6,7]，target=7，画图如下：

class Solution:
　　def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
　　　　res=[]
　　　　candidates.sort()
　　　　cur=[]
　　　　def back(start):
　　　　　　if sum(cur)>target:
　　　　　　　　return
　　　　　　if sum(cur)==target:
　　　　　　　　res.append(cur[:])
　　　　　　　　return
　　　　　　for i in range(start,len(candidates)):
　　　　　　　　cur.append(candidates[i])
　　　　　　　　back(i)
　　　　　　　　cur.pop()
　　　　back(0)
　　　　return res

LeetCode题解(0017)：九键手机按键的字母组合(Python)

def letterCombinations(self, digits: str) -> List[str]:
　　phone = {"2": ["a", "b", "c"],
　　　　　　"3": ["d", "e", "f"],
　　　　　　"4": ["g", "h", "i"],
　　　　　　"5": ["j", "k", "l"],
　　　　　　"6": ["m", "n", "o"],
　　　　　　"7": ["p", "q", "r", "s"],
　　　　　　"8": ["t", "u", "v"],
　　　　　　"9": ["w", "x", "y", "z"]}

　　ans = [""]
　　for d in digits:
　　　　if d in phone:
　　　　　　new = []
　　　　　　for item in ans:
　　　　　　　　for c in phone[d]:
　　　　　　　　　　new.append(item + c)
　　　　　　　　　　ans = new

　　return ans