本文共 3678 字，大约阅读时间需要 12 分钟。

递归：为了描述问题的某一状态，必须用到该状态的上一状态，而描述上一状态，又必须用到上一状态的上一状态……这种用自已来定义自己的方法，称为递归定义。形式如 f(n) = n*f(n-1), if n=0,f(n)=1.

回溯：从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到” 尽头 “的时候, 把结果储存,再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断” 回溯 “寻找解的方法, 称作” 回溯法

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。也就是手机键盘数字对应的字母的组合

• 示例 1：

输入: “23”

输出: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]

• 思路：

  2: a, b, c
  3: d, e, f
  a > d
  a > e
  a > f
  b > d
  b > e
  b > f
  …
  实现的难度在于递归体的处理边界问题，执行过程类似于树状结构，具体过程见代码

• 代码：

class Solution:    def letterCombinations(self, digits):        """        :param digits: str        :return: List[str]        """        if len(digits) == 0:            return None        dic = {
   }        dic['2'] = ['a', 'b', 'c']        dic['3'] = ['d', 'e', 'f']        dic['4'] = ['g', 'h', 'i']        dic['5'] = ['j', 'k', 'l']        dic['6'] = ['m', 'n', 'o']        dic['7'] = ['p', 'q', 'r', 's']        dic['8'] = ['t', 'u', 'v']        dic['9'] = ['w', 'x', 'y', 'z']        res = []        length = len(digits)        curStr = ''        def recur(res, index, length, curStr):        	# 结束条件            if index == length:                # print(curStr)                res.append(curStr)                return            for i in range(len(dic[digits[index]])):            	 # 递归体                recur(res, index + 1, length, curStr + dic[digits[index]][i])        recur(res, 0, length, curStr)        return res

39.组合总和

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

• 说明：

所有数字（包括 target）都是正整数。

解集不能包含重复的组合。

• 示例 1:

输入: candidates = [2,3,6,7], target = 7,

所求解集为: [ [7], [2,2,3] ]

• 示例 2:

输入: candidates = [2,3,5], target = 8,

所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]

• 思路：

用递归实现回溯法，过程类似于树的中序遍历

8-2-2-2-2 8-2-2-2-3 8-2-2-3 8-2-3-3 8-2-5 8-3-5

• 代码

class Solution:    def combinationSum(self, candidates, target):        """        :type candidates: List[int]        :type target: int        :rtype: List[List[int]]        """        candidates.sort()        # 储存结果        Solution.anslist = []        self.DFS(candidates, target, 0, [])        return Solution.anslist    def DFS(self, candidates, target, start, valuelist):        if target == 0:            return Solution.anslist.append(valuelist)        for i in range(start, len(candidates)):            if candidates[i] > target:                return            self.DFS(candidates, target -candidates[i], i, valuelist +[candidates[i]])

46.全排列

给定一个没有重复数字的序列，返回其所有可能的全排列

• 示例：

输入: [1,2,3]

输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

• 思路：按树状分层进行分析实现

  1.将列表的第0位与第0位交换（相当于不变），此时列表变为[‘a’, ‘b’, ‘c’]；
  1.1 将列表的第1位与第1位交换（相当于不变），得到列表[‘a’, ‘b’, ‘c’]；
  1.11 return
  1.12
  1.2 将列表的第1位与第2位交换，得到列表[‘a’, ‘c’, ‘b’]；

  2.将列表的第0位与第1位交换，得到列表[‘b’, ‘a’, ‘c’]；

  2.1 将列表的第1位与第1位交换（相当于不变），得到列表[‘b’, ‘a’, ‘c’]；
  2.2 将列表的第1位与第2位交换，得到列表[‘b’, ‘c’, ‘a’]；

  3.将列表的第0位与第2位交换，得到列表[‘c’, ‘b’, ‘a’]；

  3.1 将列表的第1位与第1位交换（相当于不变），得到列表[‘c’, ‘b’, ‘a’]；
  3.2 将列表的第1位与第2位交换，得到列表[‘c’, ‘a’, ‘b’]

• 代码

class Solution:    def permute(self, nums):        """        :type nums: List[int]        :rtype: List[List[int]]        """        def backtrack(position, end):            """            Find possible results using backtrack.            :param position:            :param end:            :return:            """            if position == end:                res.append(nums[:])                return            for index in range(position, end):                nums[position], nums[index] = nums[index], nums[position]                print(nums, position, index)                backtrack(position + 1, end)                nums[position], nums[index] = nums[index], nums[position]        res = []        backtrack(0, len(nums))        return res

转载地址：http://hwjmf.baihongyu.com/