http://blog.csdn.net/crystal6918/article/details/51924665
回溯算法的基本形式是“遞歸+循環(huán)”的圆，正因為循環(huán)中嵌套著遞歸，遞歸中包含循環(huán)菲饼，這才使得回溯比一般的遞歸和單純的循環(huán)更難理解
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) # 這步比較關(guān)鍵。
對于回溯绷耍，其實也是遞歸或者說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],
[]
]
給一個數(shù)組，求出所有的子數(shù)組集合差牛，要求不重復(fù)命锄。
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)
這道題最基礎(chǔ)的還是回溯法，DFS + 循環(huán)
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題偏化，多了一個條件脐恩，就是元素可以重復(fù)，最簡單的寫法是在78基礎(chǔ)上先排序再判斷要不要添加：
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]: #關(guān)鍵
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
完全自己一遍寫出侦讨，這種類型的題目典型求解思路就是應(yīng)用回溯驶冒。
其余參考解法：
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]
本質(zhì)上還是回溯法，只是需要將問題拆分為兩個子問題邓尤，再由子問題的解推出最終問題答案拍鲤。
