    ans = false
    queue = [[0, 0]]
    reached = Set[0]
    until queue.empty?
        x, w = queue.pop
        news = []
        (0..n-1).each do |i|
            if x[i] == 0
                if w + weight[i] > capacity[i]
                    news = []
                    break
                else
                    y = x + (1 << i)
                    if y == 2 ** n - 1
                        ans = true
                        break
                    elsif reached.include?(y)
                        next
                    else
                        reached << y
                        news << [y, w + weight[i]]
                    end
                end
            end
        end
        break if ans
        queue += news
    end
    puts ans ? 'Yes' : 'No'
end

