制限付き整数の組み合わせ

Question

allowed_intsの組み合わせのリストを生成する方法は、合計でgoalになりますか？

例：私がこれまでに作った何

allowed_ints=[1,2], goal=4 
combinations = [[1,1,1,1],[1,1,2],[2,1,1],[2,2],[1,2,1]] 

allowed_ints=[5, 6], goal=13 
combinations = [] 

はない作品を行います。

def combinations(allowed_ints, goal): 
    if goal > 0: 
     for i in allowed_ints: 
      for p in combinations(allowed_ints, goal-i): 
       yield [i] + p 
    else: 
     yield [] 

print list(combinations([1, 2],3)) 
[[1, 1, 1], [1, 1, 2], [1, 2], [2, 1], [2, 2]] # not what I want 

Answer 1

を行うことができます。

def combinations(allowed_ints, goal): 
    if goal > 0: 
     for i in allowed_ints: 
      for p in combinations(allowed_ints, goal-i): 
       if sum([i] + p) == goal: 
        yield [i] + p 
    else: 
     yield [] 

print list(combinations([1, 2],3)) 

出力：

[[1, 1, 1], [1, 2], [2, 1]] 

Answer 2

その後、再帰が、その後再帰が

目標> = 0とリストの要素が再帰

を失敗した後、終了できなかった

目標< 0を働いた

ゴール== 0のような3つの条件を含める必要があります

ところで、あなたは再帰を使ってすべてを行うことができます。ループの必要はありません、再帰はまた、あなたがこれを試す機能使用ループ

Answer 3

私はあなたが既に答えを選択している知っているが、私はしたかったですあなたのコードと似ていない選択肢を提供してください。

def combinations(allowed_ints, list, goal): 
    # base case: you're done 
    if sum(list) == goal: 
     print list 
    # if overshoot, stop here 
    elif sum(list) > goal: 
     pass 
    else: 
     for i in allowed_ints: 
      new_list = list[:] 
      new_list.append(i) 
      combinations(allowed_ints, new_list, goal) 

combinations([1, 2],[],4) 

それは提案の答えよりも良いませんが、別のアプローチを使用しています：あなたは再帰を使用したい場合は、私はこのような何かを示唆しています。