一、題目

1、LeetCode46：給定一個 沒有重複 數位的序列，返回其所有可能的全排列。

2、LeetCode47：給定一個可包含重複數位的序列，返回所有不重複的全排列。

二、範例

1、LeetCode46：

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

2、LeetCode47：

輸入: [1,1,2]
輸出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

三、思路

1、LeetCode46：遞迴+回溯

2、LeetCode47：遞迴+回溯+去重

四、程式碼

1、LeetCode46：

class Solution:
    def permute(self, nums: int):
        res = []

        def DFS(nums, tmp):
            if nums == []:
                res.append(tmp)
                return

            for i in range(len(nums)):
                DFS(nums[:i] + nums[i + 1:], tmp + [nums[i]])

        DFS(nums, [])
        return res

if __name__ == '__main__':
    test = [1,2,3]
    ans = [
          [1,2,3],
          [1,3,2],
          [2,1,3],
          [2,3,1],
          [3,1,2],
          [3,2,1]
        ]
    s = Solution()
    res = s.permute(test)
    print('test:', test)
    print('ans:', ans)
    print('res:', res)

2、LeetCode47：（該程式碼也可用於LeetCode46）

class Solution:
    def permuteUnique(self, nums):
        
        res = []
        nums.sort()

        def DFS(num, tmp):
            if num == []:
                res.append(tmp)
                return

            for i in range(len(num)):
                if i > 0 and num[i - 1] == num[i]:
                    continue
                DFS(num[: i] + num[i + 1: ], tmp + [num[i]])

        DFS(nums, [])
        return res


if __name__ == '__main__':
    test = [1,1,2]
    ans = [
          [1,1,2],
          [1,2,1],
          [2,1,1]
        ]
    s = Solution()
    res = s.permuteUnique(test)
    print('test:', test)
    print('ans:', ans)
    print('res:', res)

LeetCode46 && LeetCode47:全排列

一、題目

二、範例

三、思路

四、程式碼