# Backtracking!!!
#
# Taken from https://leetcode.com/problems/subsets/discuss/27281/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partitioning
# These are ruby translations of some general approaches to Backtracking

module Subsets
  def solve(nums)
    list = []
    backtrack(list, [], nums, 0)
    list
  end

  def backtrack(list, temp, nums, start)
    puts "About to add #{temp}"
    list << temp.dup
    (start...nums.count).each do |i|
      temp << nums[i]
      backtrack(list, temp, nums, i + 1)
      temp.delete_at(temp.count - 1)
    end
  end
end

module SubsetsWithDuplicates
  def solve(nums)
    sorted = nums.sort
    [].tap { |list| backtrack(list, [], sorted, 0) }
  end

  def backtrack(list, temp, nums, start)
    list << temp.dup
    (start...nums.count).each do |i|
      next if i > start && nums[i] == nums[i - 1]
      temp << nums[i]
      backtrack(list, temp, nums, i + 1)
      temp.pop
    end
  end
end
