old_contents: """Leetcode 46. Permutations
  Medium
  
  URL: https://leetcode.com/problems/permutations/
  
  Given a collection of distinct integers, return all possible permutations.
  
  Example:
  Input: [1,2,3]
  Output:
  [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
  ]
  """
  
  class Solution(object):
      def permute(self, nums):
          """
          :type nums: List[int]
          :rtype: List[List[int]]
          """
          pass
  
  
  def main():
      pass
  
  
  if __name__ == '__main__':
      main()
  
new_contents: """Leetcode 46. Permutations
  Medium
  
  URL: https://leetcode.com/problems/permutations/
  
  Given a collection of distinct integers, return all possible permutations.
  
  Example:
  Input: [1,2,3]
  Output:
  [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
  ]
  """
  
  class Solution(object):
      def _backtrack(self, permutations, temps, nums):
          if len(temps) == len(nums):
              # One of permutations is completed.
              permutations.append(temps[:])
          else:
              for i in range(len(nums)):
                  # If num i was used, skip it; otherwise add it to temps.
                  if nums[i] in temps:
                      continue
                  temps.append(nums[i])
  
                  # Apply DFS by recursion with backtracking.
                  self._backtrack(permutations, temps, nums)
                  temps.pop()
  
      def permute(self, nums):
          """
          :type nums: List[int]
          :rtype: List[List[int]]
          """
          permutations = []
          self._backtrack(permutations, [], nums)
          return permutations
  
  
  def main():
      nums = [1, 2, 3]
      print Solution().permute(nums)
  
  
  if __name__ == '__main__':
      main()
  
subject: Complete sol by backtracking