0040-combination-sum-ii.rb

# frozen_string_literal: true

# 40. Combination Sum II
# https://leetcode.com/problems/combination-sum-ii
# Medium

=begin
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:
Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]


Constraints:
* 1 <= candidates.length <= 100
* 1 <= candidates[i] <= 50
* 1 <= target <= 30
=end

# @param {Integer[]} candidates
# @param {Integer} target
# @return {Integer[][]}
defcombination_sum2(candidates,target)
res_array=[]
candidates.sort!
stack=[[[],0,target]]

while !stack.empty?
temp,start,remaining=stack.pop

ifremaining == 0
res_array.push(temp)
next
end

(start...candidates.length).eachdo |i|
nextifi > start && candidates[i] == candidates[i - 1]# skip duplicates
breakifcandidates[i] > remaining
stack.push([temp + [candidates[i]],i + 1,remaining - candidates[i]])
end
end

res_array
end

# **************** #
# TEST #
# **************** #

require"test/unit"
classTest_combination_sum2 < Test::Unit::TestCase
deftest_
assert_equal[[1,1,6],[1,2,5],[1,7],[2,6]].sort,combination_sum2([10,1,2,7,6,1,5],8).sort
assert_equal[[1,2,2],[5]].sort,combination_sum2([2,5,2,1,2],5).sort
end
end