ある数になる全ての組み合わせを出力する

Question

入力データとして下記があり、

candidates = [2,3,6,7], target = 7

このような結果を得たいです。

出力: [[2,2,3],[7]]

与えられた候補の中から合計がtargetになる組み合わせを全て出力したいです。
自分なりにプログラムを組んでみましたが、並びが違うだけの同じ数の組み合わせが出力されてしまってうまく行きませんでした。
このアルゴリズム問題の解き方と、考え方がわかる方がいらっしゃいましたら、ご教授いただけますと幸いです。

def combination_sum(candidates, target)
 result = []
 (1..target).each do |num|
     candidates.repeated_combination(num).to_a.each do |pair|
         if pair.sum == target
             result.push(pair)
         end
     end
 end
 result
end

# [[7],[2,2,3],[2,3,2],[3,2,2]]


この場合、[[7],[2,2,3]]なってしまって[[2,2,3],[7]]にならないのと、単純に処理時間がかかってTimeOutしてしまうようです。

Comments

[masa_engin]

def combination_sum(candidates, target)
result = []
pp
(1..target).each do |num|
candidates.repeated_combination(num).to_a.each do |pair|
if pair.sum == target
result.push(pair)
end
end
end
result
end
この場合、[[7],[2,2,3]]なってしまって[[2,2,3],[7]]にならないのと、単純に処理時間がかかってTimeOutしてしまうようです。

[BeatStar]

> ...この場合、[[7],[2,2,3]]なってしまって[[2,2,3],[7]]にならないのと...

追記はここに書かずに質問本文に追記してください。
そこに書かれても見逃してしまいます。
質問は編集できるので編集しましょう。

Answer 1

Rubyはほとんど使ったことがないので、コードが拙いのはご容赦ください。あと、もっと良い方法があるかもしれません。

まずは候補を[2,3,6,7]に固定したコードを書いてみましょう。

2,3,6,7のそれぞれの使用回数について、そのすべての組み合わせを考えて、足した結果が target になるものを収集すればよさそうです。
target が 7 の場合、2の使用回数は0～3回のいずれかになるはずです。(4回だと target を超えてしまう)
ここで、最大回数は target を 2 で割った結果となることに注意しましょう。
同様に3の使用回数は0～2回、6の使用回数は0～1回、7の使用回数は0～1回のいずれかになるはずです。

これらをネストしたループで繰り返して、和が target になるものを収集すると考えると、以下のようなコードになります。
([2,2,3]が[7]の前に来るように、ループは逆順に回しています)

def combination_sum(target)
  result = []
  (target / 2).downto(0) do |n2|
    (target / 3).downto(0) do |n3|
      (target / 6).downto(0) do |n6|
        (target / 7).downto(0) do |n7|
          if 2 * n2 + 3 * n3 + 6 * n6 + 7 * n7 == target
            result << [2] * n2 + [3] * n3 + [6] * n6 + [7] * n7
          end
        end
      end
    end
  end
  result
end

さて、これを任意の候補でやりたいのですが、候補の数だけネストを深くしなければならないので、簡単にはいきません。
やり方としては、以下の2通りが考えられます。

1. Array の product を使う
2. 再帰を使う

まず 1. ですが、Array の product は、複数の配列から要素を選ぶ組み合わせのパターンをすべて列挙できます。
そのため、それぞれの候補の使用回数の配列を渡せば、1つのループで多重ループと同じことができます。
ただ、候補が1つもない場合は対応できないので別途処理する必要があります。
さらに、Array の product はやたらメモリを使うらしく、少し候補が増えると計算できなくなります。

def combination_sum(candidates, target)
  return (target == 0) ? [[]] : [] if candidates.empty?
  result = []
  as = candidates.map{|c| (target / c).downto(0).to_a}
  a = as.shift
  a.product(*as) do |ns|
    if candidates.zip(ns).map{|c, n| c * n}.sum == target
      result << candidates.zip(ns).map{|c, n| [c] * n}.sum([])
    end
  end
  result
end  

次に2.の再帰を使う方法についてですが、以下のページが詳しいです。

よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜

こちらのページに従うと、以下のようなコードになります。(面倒なのでグローバル変数を使っています)

def combination_sum(candidates, target)
  $candidates = candidates
  $target = target
  $result = []
  dfs([])
  $result
end

def dfs(ns)
  if ns.size == $candidates.size
    if $candidates.zip(ns).map{|c, n| c * n}.sum == $target
      $result << $candidates.zip(ns).map{|c, n| [c] * n}.sum([])
    end
    return
  end
  ($target / $candidates[ns.size]).downto(0) do |n|
    ns.push(n)
    dfs(ns)
    ns.pop
  end
end

---

以下は以前の回答。

再帰を使う場合は以下のようになります。
候補から合計がtargetになる組み合わせを求める際には、候補の先頭の値を使う場合と使わない場合の2つに場合分けできます。
使う場合については、先頭の値の分だけ減らしたtargetを目標とした組み合わせを求めておいて、それらの前に先頭の値を追加すれば求められます。問題の例なら、combination_sum([2,3,6,7],7-2)を求めて([[2,3]])、それぞれの先頭に2を追加します([[2,2,3]])。
使わない場合については、単純に先頭の値を除いた候補からtargetを目標とした組み合わせを求めればよいです。問題の例なら、combination_sum([3,6,7],7)を求めます([[7]])。
あとは、再帰なので終了条件を適当に決めてあげれば、以下のように書けます。

def combination_sum(candidates, target)
  if target == 0
    [[]]
  elsif target < 0 || candidates.empty?
    []
  else
    head, *tail = candidates
    combination_sum(candidates, target - head).map{|s| [head] + s} + combination_sum(tail, target)
  end
end

上記をボトムアップにしたり計算順を逆転させたりすると、動的計画法での解になります。
面倒なので、以下では一次元の表を上書きする形としています。

def combination_sum(candidates, target)
  dp = [[[]]] + [[]] * target
  candidates.each do |c|
    (0..target - c).each do |i|
      dp[i + c] += dp[i].map{|s| s + [c]}
    end
  end
  dp[-1]
end

---

過去に同じ問題に回答していたので、リンクを貼っておきます。(ただし言語はPython)
combination sumを可読性の高いコードで計算する方法

Answer 2

これを見る限り、repeated_combinationを使えばいいんだと思います。

permutationは順列、つまり { 1, 2 } と { 2, 1 } は別のものとして認識して計算する。数学だと 3P2 とか。
combinationは組み合わせ、{ 1, 2 } と { 2, 1 } は同じものとして重複しない計算。数学だと 3C2 とか。

---

...この場合、[[7],[2,2,3]]なってしまって[[2,2,3],[7]]にならない

必ず [[7],[2,2,3]] ですか? 単に組み合わせを求めるなら順番は関係ないはずです。もしかして競技プログラミングとかそういうのでしょうか?
それならちゃんとそういう定義を書くべきです。

もし単純に[7]から始めたいのなら、「配列の要素数でソートする」とかが考えられます。

単純に処理時間がかかってTimeOutしてしまう

それならrepeated_combination系を使わなければいいです。ざっと見ただけなのでわかりませんが、repeated_ が付いていない方はどうでしょうか?
計算量を意識して考えてみてください。

私の考えでは、「動的計画法」か「bit全探索」辺りでやる…ですかね。

「bit全探索 部分和」とかで検索してみてください。