回溯

返回首页

返回算法分类分析

第一题 Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example, If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解法

这个方法值得好好记住。

class Solution(object):
def fun(self, res, i, n, k, tmp):
    if k == 0:
        res.append(tmp)
        return
    for j in xrange(i+1, n):
        if j < n - k + 1:
            self.fun(res, j, n, k-1, tmp + [j])

def combine(self, n, k):
    """
    :type n: int
    :type k: int
    :rtype: List[List[int]]
    """
    res = []
    self.fun(res, 0, n+1, k, [])
    return res

第二题 Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

    [
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]

解法

class Solution(object):
def generateParenthesis(self, n):
    """
    :type n: int
    :rtype: List[str]
    """
    res = []

    def dfs(open_count, remaining, currString):
        if not remaining > 0 and not open_count > 0:
            res.append(currString)
        elif open_count > 0:
            dfs(open_count - 1, remaining, currString + ")")
        if remaining > 0:
            dfs(open_count + 1, remaining - 1, currString + "(")

    dfs(0, n, "")

    return res

第三题 Combination Sum

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is: 

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

解法

class Solution(object):
def combinationSum2(self, candidates, target):
    results = set()
    self._combinationSum2(sorted(candidates, reverse=True), target, results, (), 0)
    results = [list(result) for result in results]
    return results

def _combinationSum2(self, candidates, target, results, progress, sum):
    if sum == target:
        results.add(progress)
        return
    if sum > target or not candidates:
        return
    for i, c in enumerate(candidates):
        new_progress = progress + (c,)
        new_sum = sum + c
        self._combinationSum2(candidates[i+1:], target, results, new_progress, new_sum)

第四题 Letter Combinations of a Phone Number

Given a digit string, 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.

Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

解法

class Solution(object):
def __init__(self):
    self.memo = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}

def letterCombinations(self, digits):
    if not digits:
        return []
    res = []
    self.dfs(digits, 0, "", res)
    return res


def dfs(self,digits,idx,path,res):
    if idx==len(digits):   
        res.append(path)
        return
    for c in self.memo[digits[idx]]:
        self.dfs(digits,idx+1,path+c,res)