程序代码：

#最短加法链问题
m=eval(input("请输入目标数："))
chain=[1,2]
best_chain=[]
depth=0
found=False  #判断是否找到加法链
sumN=1
def back(step):
    global found
    global chain
    global best_chain
    global depth
    check=[]
    for x in range(10000):
        check.append(0)
    if step-1==depth:
        if chain[step-1]==m:
            found=True  #找到加法链
            best_chain=chain*1
        return
    for i in range(1,step+1):  #遍历子结点
        for j in range(1,i+1)[::-1]:
            if chain[i-1]+chain[j-1]<=chain[step-1]:
            #剪枝，下一层结点值必须大于上一层
                break
            if chain[i-1]+chain[j-1]<=n:
                #剪枝，只关心比n小的子结点
                if check[chain[i-1]+chain[j-1]==1:
                    continue #就是这里一直有错
                check[chain[i-1]+chain[j-1]]=1
                n=chain[i-1]+chain[j-1]
                for t in range(step,depth):
                #计算depth内，以m为根的子树中的最大结点
                    n=n*2
                if n<m:#判断n是否在以m为根的子树中
                      continue
                if len(chain)==step:
                    chain.append(chain[i-1]+chain[j-1])
                else:
                    chain[step]=chain[i-1]+chain[j-1]
                back(step+1)
                if found:#找到加法链
                    return
while(sumN<m):
    depth=depth+1
    sumN=sumN*2
if m!=1:
    while not found:
        back(2)
        depth=depth+1
        #depth为下界，表示加法链最短可以是depth(从0开始算)
    print("最短加法链为：{}".format(best_chain))
else:
    print(1)