Rubyで理解する蟻本「2−1再起関数部分和問題」

深さ優先探索による部分和問題の解法

部分和問題(DFS 深さ優先探索)

問題

与えられた a1, a2, ..., an からいくつか選び、その和を k にすることができるか判定する

入力

n
a1, a2, ..., an
k

例

4
1, 2, 4, 7
13
-> Yes(13 = 2 + 4 + 7)

実装

@n = gets.to_i
@array = gets.chomp.split(" ").map(&:to_i)
@k = gets.to_i

def depth_first_search(i, sum)
  return false if sum > @k   # 合計が既にkを超えていたらfalse
  return sum == @k if i == @n # 最後の要素までいったら合計とsumを比較

  # 要素iの値を使用する場合
  return true if depth_first_search(i + 1, sum + @array[i])
  # 要素iの値を使用しない場合、sumに足さない
  return true if depth_first_search(i + 1, sum)

  return false
end

puts depth_first_search(0, 0) ? "Yes" : "No"