首页 > 代码库 > 递归实现:从给定的字典中抽出所有相加值SUM的全部组合

递归实现:从给定的字典中抽出所有相加值SUM的全部组合

递归的话,只需要考虑第一个数字的两种情况:选择或者不选择

class Dic:
    def __init__(self,id,values):
        self.id = id
        self.values = values

def fun(dic,res,target,index):
    if target == 0:
        print res
        return
    if index == len(dic)-1:
        return
    #not choice this
    fun(dic,res,target,index+1)
    #choice this
    res += dic[index].id
    target -= dic[index].values
    fun(dic,res,target,index+1)

if __name__ == __main__:
    dic1 = Dic("X001",1)
    dic2 = Dic("X002",3)
    dic3 = Dic("X003", 4)
    dic4 = Dic("X004", 5)
    dic5 = Dic("X005", 9)
    dic6 = Dic("X00", 11)
    dic7 = Dic("X00", 2)
    dic = [dic1,dic2,dic3,dic4,dic5,dic6,dic7]
    res = ""
    target = 9
    fun(dic,res,target,0)

 

递归实现:从给定的字典中抽出所有相加值SUM的全部组合