hello-algo/codes/ruby/chapter_backtracking/subset_sum_i_naive.rb
khoaxuantu aa818945f0
feat: Add Ruby code - chapter "Backtracking" (#1373)
* [feat] add ruby code - chapter backtracking

* feat: add ruby code block - chapter backtracking
2024-05-24 15:41:40 +08:00

46 lines
1.2 KiB
Ruby
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

=begin
File: subset_sum_i_naive.rb
Created Time: 2024-05-22
Author: Xuan Khoa Tu Nguyen (ngxktuzkai2000@gmail.com)
=end
### 回溯算法:子集和 I ###
def backtrack(state, target, total, choices, res)
# 子集和等于 target 时,记录解
if total == target
res << state.dup
return
end
# 遍历所有选择
for i in 0...choices.length
# 剪枝:若子集和超过 target ,则跳过该选择
next if total + choices[i] > target
# 尝试:做出选择,更新元素和 total
state << choices[i]
# 进行下一轮选择
backtrack(state, target, total + choices[i], choices, res)
# 回退:撤销选择,恢复到之前的状态
state.pop
end
end
### 求解子集和 I包含重复子集###
def subset_sum_i_naive(nums, target)
state = [] # 状态(子集)
total = 0 # 子集和
res = [] # 结果列表(子集列表)
backtrack(state, target, total, nums, res)
res
end
### Driver Code ###
if __FILE__ == $0
nums = [3, 4, 5]
target = 9
res = subset_sum_i_naive(nums, target)
puts "输入数组 nums = #{nums}, target = #{target}"
puts "所有和等于 #{target} 的子集 res = #{res}"
puts "请注意,该方法输出的结果包含重复集合"
end