http://blog.csdn.net/crystal6918/article/details/51924665
回溯算法的基本形式是“递归+循环”，正因为循环中嵌套着递归，递归中包含循环，这才使得回溯比一般的递归和单纯的循环更难理解
46. Permutations
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.result = []
sub = []
self.dfs(nums,sub)
return self.result
def dfs(self, nums, sub):
if len(sub) == len(nums):
print sub
self.result.append(sub[:])
for m in nums:
if m in sub:
continue
sub.append(m)
self.dfs(nums, sub)
sub.remove(m) # 这步比较关键。
对于回溯，其实也是递归或者说DFS，需要深入骨灰级理解。上面这道题还有一些疑问，也不够熟练。整道题不是很难，多接触。
39. Combination Sum
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is
[
[7],
[2, 2, 3]
]
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
self.helper(res, candidates, [], target, 0)
return res
def helper(self, res, candidates, subres, target, index):
if target == 0:
res.append(subres[:])
if target < 0:
return
for i in xrange(index, len(candidates)):
subres.append(candidates[i])
self.helper(res, candidates, subres, target - candidates[i], i)
subres.pop()
40. Combination Sum II
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):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
candidates = sorted(candidates)
self.helper(res, candidates, target, [], 0)
return res
def helper(self,res, candidates, target, subres, index):
if target == 0:
res.append(subres[:])
if target < 0:
return
for i in xrange(index, len(candidates)):
if i > index and candidates[i] == candidates[i-1]:
continue
subres.append(candidates[i])
self.helper(res, candidates, target - candidates[i], subres, i + 1)
subres.pop()
77、 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 combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
result = []
self.helper(n, 0, [], k, result)
return result
def helper(self, n, start, sub, k, result):
if k == 0:
result.append(sub[:])
for i in xrange(start, n):
sub.append(i+1)
self.helper(n, i+1, sub, k - 1, result)
sub.pop()
上述程序在输入为20，16就超时了。上面为普通思路，Java可以通过，python却不行。
下面方法不是通用的，需要好好理解。
def combine(self, n, k):
ans = []
stack = []
x = 1
while True:
l = len(stack)
if l == k:
ans.append(stack[:])
if l == k or x > n - k + l + 1:
if not stack:
return ans
x = stack.pop() + 1
else:
stack.append(x)
x += 1
78. Subsets
https://www.youtube.com/watch?v=Az3PfUep7gk
上述视频讲解的比较清楚，适合梳理。
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
给一个数组，求出所有的子数组集合，要求不重复。
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.res = []
def dfs(nums, sub, index):
self.res.append(sub[:])
for i in xrange(index, len(nums)):
sub.append(nums[i])
dfs(nums, sub, i + 1)
sub.pop()
dfs(nums, [], 0)
return self.res
79. Word Search
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
m = len(board)
if m == 0:
return False
n = len(board[0])
if n == 0 or word is None:
return False
visited = [[False for _ in xrange(n)] for _ in xrange(m)]
for i in xrange(m):
for j in xrange(n):
if self.dfs(board, i, j, visited, word, 0, m, n):
return True
return False
def dfs(self, board, i, j, visited, word, pos, m, n):
if pos == len(word):
return True
if i < 0 or j < 0 or i >= m or j >= n:
return False
if visited[i][j] or board[i][j] != word[pos]:
return False
visited[i][j] = True
res = self.dfs(board, i - 1, j, visited, word, pos + 1, m, n) or \
self.dfs(board, i + 1, j, visited, word, pos + 1, m, n) or \
self.dfs(board, i, j - 1, visited, word, pos + 1, m, n) or \
self.dfs(board, i, j + 1, visited, word, pos + 1, m, n)
visited[i][j] = False
return res
93. Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
这道题最基础的还是回溯法，DFS + 循环
class Solution(object):
def restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
self.res = []
self.dfs(s, '', 0, 0)
return self.res
def dfs(self, s, subres, count, index):
if count > 4:
return
if count == 4 and index == len(s):
self.res.append(subres)
return
for i in xrange(0, 3):
if index + i + 1 > len(s):
break
temp = s[index:index + i + 1]
if (temp.startswith('0') and len(temp) > 1) or int(temp) >= 256:
continue
self.dfs(s, subres + temp + ('' if count == 3 else '.'), count + 1, index + i + 1)
216. Combination Sum III
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
class Solution(object):
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
self.res = []
self.helper(n, k, [], 1)
return self.res
def helper(self, n, k, subres, index):
if k == 0:
return
for item in xrange(index,10):
if item > n:
break
subres.append(item)
if item == n and k == 1:
self.res.append(subres[:])
if item < n and k > 1:
self.helper(n - item, k - 1, subres, item + 1)
subres.pop()
简化：
class Solution1(object):
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
self.res = []
self.helper(n, k, [], 1)
return self.res
def helper(self, n, k, subres, index):
if k == 0 and n == 0:
self.res.append(subres[:])
return
if k < 0:
return
for item in xrange(index, 10):
if item > n:
break
subres.append(item)
self.helper(n - item, k - 1, subres, item + 1)
subres.pop()
90. Subsets II
这个题相比于78题，多了一个条件，就是元素可以重复，最简单的写法是在78基础上先排序再判断要不要添加：
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.res = []
nums = sorted(nums)
self.helper(nums, [], 0)
return self.res
def helper(self, nums, subset,start):
self.res.append(subset[:])
for i in xrange(start, len(nums)):
if i != start and nums[i] == nums[i-1]: #关键
continue
subset.append(nums[i])
self.helper(nums, subset, i + 1)
subset.pop()
22. 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]
"""
self.res = []
self.helper('', 0, 0, n)
return self.res
def helper(self, s, left, right, n):
if len(s) == 2 * n:
self.res.append(s)
return
if left < n:
self.helper(s + '(', left + 1, right, n)
if left > right:
self.helper(s + ')', left, right + 1, n)
17 Letter Combinations of a Phone Number
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if digits == '':
return []
self.DigitDict=[' ','1', "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
res = ['']
for d in digits:
res = self.letterCombBT(int(d),res)
return res
def letterCombBT(self, digit, oldStrList):
return [dstr+i for i in self.DigitDict[digit] for dstr in oldStrList]
class Solution1(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if digits == '':
return []
self.res = []
self.DigitDict = [' ', '1', "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
self.helper(digits, '', 0)
return self.res
def helper(self, digits, subres, index):
if index == len(digits):
self.res.append(subres[:])
return
for i in self.DigitDict[int(digits[index])]:
subres += i
self.helper(digits, subres, index + 1)
subres = subres[:-1]
131. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
self.res = []
self.helper(s, [], 0)
return self.res
def helper(self, s, subres, index):
if index == len(s):
self.res.append(subres[:])
return
for i in xrange(index, len(s)):
if self.ispalindrime(s[index:i+1]):
subres.append(s[index:i+1])
self.helper(s, subres, i+1)
subres.pop()
def ispalindrime(self,s):
length = len(s)
left, right = 0, length - 1
while left < right:
if s[left] != s[right]:
return False
left, right = left + 1, right - 1
return True
完全自己一遍写出，这种类型的题目典型求解思路就是应用回溯。
其余参考解法：
class Solution:
# @param s, a string
# @return a list of lists of string
def partition(self, s):
n = len(s)
is_palindrome = [[0 for j in xrange(n)] for i in xrange(n)]
for i in reversed(xrange(0, n)):
for j in xrange(i, n):
is_palindrome[i][j] = s[i] == s[j] and ((j - i < 2 ) or is_palindrome[i + 1][j - 1])
sub_partition = [[] for i in xrange(n)]
for i in reversed(xrange(n)):
for j in xrange(i, n):
if is_palindrome[i][j]:
if j + 1 < n:
for p in sub_partition[j + 1]:
sub_partition[i].append([s[i:j + 1]] + p)
else:
sub_partition[i].append([s[i:j + 1]])
return sub_partition[0]
357. Count Numbers with Unique Digits
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])
class Solution(object):
def countNumbersWithUniqueDigits(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 1
count, fk = 10, 9
for k in xrange(2, n+1):
fk *= 10 - (k-1)
count += fk
return count
这道题没有深入，只是稍微带过了，有两种主流方法，一是math trick，二是回溯。
401. Binary Watch
A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).
Each LED represents a zero or one, with the least significant bit on the right.
For example, the above binary watch reads "3:25".
Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
Example:
Example:
Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
class Solution(object):
def readBinaryWatch(self, num):
"""
:type num: int
:rtype: List[str]
"""
self.res = []
lookup1, lookup2 = [8,4,2,1], [32,16,8,4,2,1]
for i in xrange(num+1):
res1, res2 = [], []
self.helper(lookup1, i, res1, 0)
self.helper(lookup2, num - i, res2, 0)
for item in res1:
if item >= 12:
continue
for value in res2:
if value >= 60:
continue
else:
temp = str(value) if value >= 10 else '0' + str(value)
self.res.append(str(item) + ':' + temp)
return self.res
def helper(self, lookup, count, res, subres):
if count == 0:
res.append(subres)
return
for i in xrange(len(lookup)):
subres += lookup[i]
self.helper(lookup[i+1:], count-1, res, subres)
subres -= lookup[i]
本质上还是回溯法，只是需要将问题拆分为两个子问题，再由子问题的解推出最终问题答案。
