###### tags: `Leetcode` `medium` `backtracking` `python` `Top 100 Liked Questions`

# 46. Permutations

## [題目連結:] https://leetcode.com/problems/permutations/

## 題目:
Given an array ```nums``` of distinct integers, return all the possible permutations. You can return the answer in **any order**.

**Example 1:**

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

**Example 2:**

Input: nums = [0,1]
Output: [[0,1],[1,0]]

**Example 3:**

Input: nums = [1]
Output: [[1]]

## 解題想法:
兄弟題目: [47. Permutations II](/IL-bgYWuSIm8ohc5nKqsCw)
* 題目為: 給一數組，求其所有的排列組合

## Python: (Sol1)
* 遞迴求解:
* pos紀錄當前的位置，分別對於pos後面的位置與pos交換，遞迴求解

class Solution:
    def permute(self, nums):
        #遞歸函數
        self.res = []
        self.dfs(nums, 0, [])
        return self.res
    def dfs(self,nums,pos,path):
            #交換位置是最後那麼已完成當前排列
            if pos == len(nums):
                self.res.append(path)
                return
            for i in range(pos, len(nums)):
                #i與pos交換
                nums[i], nums[pos] = nums[pos], nums[i]
                #進入遞歸
                self.dfs(nums, pos + 1, path+[nums[pos]])
                #遞歸完成i與pos交換回來
                nums[i], nums[pos] = nums[pos], nums[i]
                    
if __name__ == '__main__':
    result = Solution()
    ans = result.permute(nums = [1,2,3])
    print(ans)

## Python: (Sol2)
* Recursive:
* 選pos輪流當頭，配上nums去掉nums[pos]後進行遞迴

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        #init
        res=[]
        if len(nums)==0 or len(nums)==1:
            res.append(nums)
            return res
        #遞迴找去掉pos之num
        for pos in range(len(nums)):
            #nums[:pos] + nums[pos+1:]->移除nums[pos]的元素
            for val in self.permute(nums[:pos]+nums[pos+1:]):
                res.append([nums[pos]]+val)
        return res

if __name__ == '__main__':
    result = Solution()
    ans = result.permute(nums = [1,2,3])
    print(ans)

## Python: Sol3
參考 [47. Permutations II](/IL-bgYWuSIm8ohc5nKqsCw) 概念

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.res=[]
        visited=[False]*len(nums) #紀錄該位置是否拜訪過
        self.dfs(nums,[],visited)
        return self.res
    def dfs(self,nums,path,visited):
        if len(path)==len(nums):
            self.res.append(path)
            return 
        for i in range(len(nums)):
            if visited[i]: #若該位置已經訪問過，跳過
                continue
            visited[i]=True
            self.dfs(nums,path+[nums[i]],visited)
            visited[i]=False