回溯法的基本思想：
回溯法（探索與回溯法）是一種選優(yōu)搜索法，又稱為試探法峻黍，按選優(yōu)條件向前搜索复隆，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時姆涩，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)挽拂，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法骨饿，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”亏栈。
經(jīng)典例子：
回溯法子集樹解決數(shù)字組合問題
1.問題：
找出從自然數(shù)1、2宏赘、3绒北、...、n中任取r個數(shù)的所有組合（組合需要有序）察署。
例如闷游，n=5，r=3的所有組合為：
1,2,3贴汪；1,2,4脐往；1,2,5；1,3,4扳埂；1,3,5业簿；1,4,5；2,3,4阳懂；2,3,5梅尤；2,4,5；3,4,5岩调；
2.分析：
1.解空間樹的動態(tài)搜索：在搜索至樹中任一節(jié)點時克饶，先判斷該節(jié)點對應(yīng)的部分是否是滿足約束條件，或者是否超出目標(biāo)函數(shù)的界誊辉，也就是判斷該節(jié)點是否包含問題的最優(yōu)解矾湃。如果肯定不包含，則跳過對該節(jié)點為根的子樹的搜索堕澄，即所謂的剪枝邀跃；否則霉咨，進(jìn)入該節(jié)點為根的子樹，繼續(xù)按照深度優(yōu)先策略搜索拍屑。
2.子集樹：但所有的問題是從n個元素的集合中找出滿足某種性質(zhì)的子集時途戒，相應(yīng)的解空間樹成為子集樹
3.此題中r=3的所有組合，相當(dāng)于元素個數(shù)為3的所有子集僵驰。因此喷斋，在遍歷子集樹的時候，對元素個數(shù)不為3的子樹剪枝即可蒜茴。
# Author:Iron
'''數(shù)字組合問題'''
n = 5
r = 3
a = [1,2,3,4,5] # 五個數(shù)字
x = [0]*n # 一個解（n元0,1數(shù)組） 固定長度
X = []? # 一組解
def conflict(k):
? global n, r, x
? if sum(x[:k+1]) > r: # 部分解的長度超出r
? ? return True
? if sum(x[:k+1]) + (n-k-1) < r: # 部分解的長度加上剩下長度不夠r
? ? return True
? return False # 無沖突
# 套用子集樹模板
def comb(k): # 到達(dá)第k個元素
? global n, x, X
? if k >= n: # 超出最尾的元素
? ? #print(x)
? ? X.append(x[:]) # 保存（一個解）
? else:
? ? for i in [1, 0]: # 遍歷元素 a[k] 的兩種選擇狀態(tài):1-選擇星爪，0-不選
? ? ? x[k] = i
? ? ? if not conflict(k): # 剪枝
? ? ? ? comb(k+1)
# 根據(jù)一個解x，構(gòu)造對應(yīng)的一個組合
def get_a_comb(x):
? global a
? return [y[0] for y in filter(lambda s:s[1]==1, zip(a, x))]
# 根據(jù)一組解X粉私，構(gòu)造對應(yīng)的一組組合
def get_all_combs(X):
? return [get_a_comb(x) for x in X]
# 測試
comb(0)
print(X)
print(get_all_combs(X))
#運行結(jié)果
'''
[[1, 1, 1, 0, 0], [1, 1, 0, 1, 0], [1, 1, 0, 0, 1], [1, 0, 1, 1, 0],
[1, 0, 1, 0, 1], [1, 0, 0, 1, 1], [0, 1, 1, 1, 0], [0, 1, 1, 0, 1],
[0, 1, 0, 1, 1], [0, 0, 1, 1, 1]]
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5],
[2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
'''
