1

最終的にTrueが返されたときに見つかった値を出力できるように、サブセット合計の問題のコードを変更する方法を見つけようとしています。私の現在の実装は再帰的に機能し、メモ化を利用していますが、それを変更して保存し、最終的に目的の合計に達するパスを返す方法がわかりません。

私はそれの再帰性を破棄し、代わりに反復を使用しようとしましたが、次の値を使用しない場合と使用する場合の両方を処理するために、for ループ内でコードをレイアウトする方法がわかりませんそれ。

注：この実装では、値は一度しか使用できません。元の「サブセット合計」の問題がそれを強制するかどうかはわかりません...

def subsetSum(tot, vals, mem={}):
  key = (tot, len(vals))
  if key not in mem:
    if tot == 0:
      mem[key] = True
      return True
    if tot < 0 or len(vals) == 0:
      mem[key] = False
      return False
    return subsetSum(tot, vals[:-1], mem) or 
           subsetSum(tot-vals[-1], vals[:-1], mem)
  else:
    return mem[key]

これを変換する方法に関するヘルプやヒントは大歓迎です。今後のインタビューの練習としてこれをやっています。

4

1 に答える 1

1

関数の呼び出し中に print を使用できます。関数のさまざまな条件を満足させるために、さまざまな値で関数を呼び出してみてください。

例えば：

print subsetSum(tot, vals, mem)

または、値を表示したい場所に関数に print ステートメントを追加することもできます。

例えば：

def subsetSum(tot, vals, mem={}):
  key = (tot, len(vals))
  if key not in mem:
    if tot == 0:
      mem[key] = True
      return True
    if tot < 0 or len(vals) == 0:
       print tot, len(vals)   #Added a print statement here
       mem[key] = False
       return False
    return subsetSum(tot, vals[:-1], mem) or 
           subsetSum(tot-vals[-1], vals[:-1], mem)
  else:
    return mem[key]
于 2014-03-09T02:46:12.253 に答える