输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

def backtrack(n, nums, output, first)
    puts "#{first}-#{nums}"
    if (n == first)
        # puts "---------"
        output.push(nums.dup)        
        #puts "#{first}-#{output.inspect}"
        return
    end
    (first..n - 1).each do |i|
        nums[i], nums[first] = nums[first], nums[i]
        puts "#{i}-#{first}-#{nums.inspect}"
        backtrack(n, nums, output, first + 1)
        nums[i], nums[first] = nums[first], nums[i]    
    end    
end    

def permute(nums)
    output = []
    n = nums.size
    backtrack(n, nums, output, 0)
    output
end