LeetCode Combination Sumを解いた

問題

leetcode.com

ヒントなしで解いた結果

全ての配列の値が1になると仮定したら最大でtarget / 1 の個数の配列が必要になることが分かった。 だから何も考えずに配列から重複ありで最大でtarget / 1 個の配列の組み合わせリストを作成して合計値がtargetになるやつを絞り込めば良いと思った。

# @param {Integer[]} candidates
# @param {Integer} target
# @return {Integer[][]}
def combination_sum(candidates, target)
    result = []
    target.to_i.times do |i|
      candidates.repeated_combination(i + 1).to_a.each do |arr|
        result << arr  if arr.sum == target
      end
    end
    p result
end

結果として Time Limit Exceededになってしまった。よく考えて数学の公式を思い出して計算してみればループの回数が必然的に大きなるということに気づいた。

manabitimes.jp

ヒントありで解いた結果

問題文をよく読むと All elements of candidates are distinct.と書いてあるから全て1になるというテストケースは想定していないということに気づいたのと、全探索をせずに途中で条件を満たさないとなったらどんどん切り捨てるバッグトラック法を知った。 バッグトラック法を使って失敗したテストケース(8個の要素を持つ配列、targetは27)を考えて計算式を書いてみたら先ほどよりもループの回数が少なくできることに気づいた。

今度は全ての配列の値が配列内の最小の値(min)になると仮定したら最大でtarget / min の個数の配列が必要になると仮定して解いた。

e-words.jp

# @param {Integer[]} candidates
# @param {Integer} target
# @return {Integer[][]}
def combination_sum(candidates, target)
    result = []
    max = target / candidates.sort[0]
    max.times do |i|
      candidates.sort.repeated_combination(i + 1).to_a.each do |arr|
        result << arr  if arr.sum == target
      end
    end
    p result
end

最終的にはクリアできた。