/
githubmirror
/
hello-algo
Обзор
Документация
Войти
/
githubmirror
/
hello-algo
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
main
en/codes/ruby/chapter_backtracking/permutations_ii.rb
48 строк
1 KB
Yudong Jin
Translate all code to English (#1836)
31 дек 2025, 02:44
Не верифицирован
31 дек 2025, 02:44
2778a6f
Код
Авторство
О чём код?
=begin File: permutations_ii.rb Created Time: 2024-05-22 Author: Xuan Khoa Tu Nguyen (ngxktuzkai2000@gmail.com) =end ### Backtracking: permutations II ### def backtrack(state, choices, selected, res) # When the state length equals the number of elements, record the solution if state.length == choices.length res << state.dup return end # Traverse all choices duplicated = Set.new choices.each_with_index do |choice, i| # Pruning: do not allow repeated selection of elements and do not allow repeated selection of equal elements if !selected[i] && !duplicated.include?(choice) # Attempt: make choice, update state duplicated.add(choice) selected[i] = true state << choice # Proceed to the next round of selection backtrack(state, choices, selected, res) # Backtrack: undo choice, restore to previous state selected[i] = false state.pop end end end ### Permutations II ### def permutations_ii(nums) res = [] backtrack([], nums, Array.new(nums.length, false), res) res end ### Driver Code ### if __FILE__ == $0 nums = [1, 2, 2] res = permutations_ii(nums) puts "Input array nums = #{nums}" puts "All permutations res = #{res}" end