在学回溯法的例子,集合求子集,遇到的问题。下面是代码:
其中加了很多print是为了更好的看程序是怎么一步步运行的。
#-*-coding:utf-8-*-
#求子集
#使用回溯法。对每个数据进行显示或不显示(1or0)的选择
def mybacktrack(a,k,data):
print "1",a,k
if is_a_solution(a,k,data):
process_solution(a,k,data)#得到解
print "2",a,k
else:
print "3",a,k
k+=1 #搜索深度+1
for i in range(2):
print "4",a,k
a.append(i)
mybacktrack(a,k,data) #递归
print "5",a,k
# a=a[:-1] #使用这一句递归后a没有变
a=a[:k-1]#改成这样就没问题
print "6",a,k
def is_a_solution(a,k,data): #判断是否是合理的解
return len(a)==len(data)
def process_solution(a,k,data):
print "{",
for j in range(len(a)):
if a[j]:
print data[j],
print "}"
data=[1,2,3,4] #集合
k=0 #初始搜索深度
a=[] #初始搜索根
mybacktrack(a,k,data)