Partitioning Souvenirs

You and two of your friends have just returned back home after visiting various countries. Now you would like to evenly split all the souvenirs that all three of you bought.

Problem Description

Input Format.

The first line contains an integer 𝑛. The second line contains integers 𝑣1, 𝑣2, . . . , 𝑣𝑛 separated by spaces.

Constraints.

1 ≤ 𝑛 ≤ 20, 1 ≤ 𝑣𝑖 ≤ 30 for all 𝑖.

Output Format.

Output 1, if it possible to partition 𝑣1, 𝑣2, . . . , 𝑣𝑛 into three subsets with equal sums, and 0 otherwise.

Example.

Input:

11 
17 59 34 57 17 23 67 1 18 2 59

Output:

(34 + 67 + 17 = 23 + 59 + 1 + 17 + 18 = 59 + 2 + 57) can be divided

number = gets.chomp.to_i
array_str = gets.chomp.split
array = array_str.map{|el| el.to_i}
sum = array.sum
target_sum = sum / 3
results = []

if number <= 2 || sum % 3 != 0
  puts 0
  return
end

if array.max > target_sum
  puts 0
  return
end

number.times.each do |i|
  array.combination(i).each{|a| results << a.sort if a.sum == target_sum}
end

uniq_results = results.uniq
if uniq_results.any? && results.length > 3
  results.combination(3).each do |comb|
    flattened = comb.flatten
    if flattened.length == number
      if array.sort == flattened.sort
        puts 1
        break
      else
        next
      end
    else
      next
    end
  end
elsif results.length == 3
  puts array.sort == results.flatten.sort ? 1 : 0
  return
else
  puts 0
  return
end