dzdzjz
dzdzjz
2018-12-24 16:38

python在递归时使用列表切片【:-1】,回归到上一层时原函数没变,描述的不太清,请看解释,希望有人解惑。

  • python

在学回溯法的例子,集合求子集,遇到的问题。下面是代码:
其中加了很多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)
  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答