Skip to content

Instantly share code, notes, and snippets.

@msg7086

msg7086/v2ex-835261-leetcode-416.rb

Last active February 20, 2022 23:25
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save msg7086/744d4cf2d81b42e27cb73069ecff939d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save msg7086/744d4cf2d81b42e27cb73069ecff939d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. msg7086 revised this gist Feb 20, 2022. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions v2ex-835261-leetcode-416.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -3,6 +3,8 @@
    def can_partition(nums)
    sum = nums.sum
    return false if sum.odd?
    nums.sort!
    nums.reverse!
    half_sum = sum / 2
    dp = Set.new
    0.upto(nums.size-1) do |i|
  2. msg7086 revised this gist Feb 20, 2022. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion v2ex-835261-leetcode-416.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -7,7 +7,7 @@ def can_partition(nums)
    dp = Set.new
    0.upto(nums.size-1) do |i|
    num = nums[i]
    dp += dp.map { |i| i + num }
    dp += dp.map { |x| x + num }
    dp << num
    return true if dp.include?(half_sum)
    dp.delete_if { |x| x > half_sum}
  3. msg7086 revised this gist Feb 20, 2022. 1 changed file with 6 additions and 7 deletions.
    13 changes: 6 additions & 7 deletions v2ex-835261-leetcode-416.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -3,15 +3,14 @@
    def can_partition(nums)
    sum = nums.sum
    return false if sum.odd?
    nums.sort!
    nums.reverse!
    half_sum = sum / 2
    dp_map = Array.new(nums.length) { |i| Set.new([nums[i]]) }
    1.upto(nums.size-1) do |i|
    dp = Set.new
    0.upto(nums.size-1) do |i|
    num = nums[i]
    dp_map[i] += 0.upto(i-1).flat_map { |j| dp_map[j].map { |k| k + num } }
    return true if dp_map[i].include?(half_sum)
    dp_map[i].delete_if { |x| x > half_sum}
    dp += dp.map { |i| i + num }
    dp << num
    return true if dp.include?(half_sum)
    dp.delete_if { |x| x > half_sum}
    end
    false
    end
  4. msg7086 created this gist Feb 20, 2022.
    17 changes: 17 additions & 0 deletions v2ex-835261-leetcode-416.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,17 @@
    # @param {Integer[]} nums
    # @return {Boolean}
    def can_partition(nums)
    sum = nums.sum
    return false if sum.odd?
    nums.sort!
    nums.reverse!
    half_sum = sum / 2
    dp_map = Array.new(nums.length) { |i| Set.new([nums[i]]) }
    1.upto(nums.size-1) do |i|
    num = nums[i]
    dp_map[i] += 0.upto(i-1).flat_map { |j| dp_map[j].map { |k| k + num } }
    return true if dp_map[i].include?(half_sum)
    dp_map[i].delete_if { |x| x > half_sum}
    end
    false
    end