46. 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]]

思路

  1. 列出所有可能性
  2. 觀察底下為 swap 後即可
  3. 合併為同一陣列輸出
  4. 深度優先

實作

result = [] # 初始化 result
# {0, 1, 2}
    #{1} -> 2
    #{2} -> 2
    #{3} -> 2
for i in range(start, len(nums)):    
    # swap 值交換，以便生成不同的排列。這是排列算法的關鍵部分，通過不斷交換元素，生成不同的排列。
    # 外層開始 nums[0] = 1
    # 外層開始 nums[1] = 2
    # 外層開始 nums[2] = 3
    nums[start], nums[i] = nums[i], nums[start]
    result += self._permuteHelper(nums, start + 1) # recursive
    # depth:1
        # [1, 2, 3]
        # [1, 3, 2] -> result
    # depth:2
        # [2, 1, 3]
        # [2, 3, 1] -> result
    # depth:3
        # [3, 2, 1]
        # [3, 1, 2] -> result
    nums[start], nums[i] = nums[i], nums[start] # 恢復 nums 列表的原始狀態，以便進行下一輪的交換操作
return result

完整代碼

class Solution(object):
  def _permuteHelper(self, nums, start=0):
    if start == len(nums) - 1:
      return [nums[:]]

    result = []
    for i in range(start, len(nums)): 
      nums[start], nums[i] = nums[i], nums[start]
      result += self._permuteHelper(nums, start + 1)
      nums[start], nums[i] = nums[i], nums[start]
 
    return result
  def permute(self, nums):
    return self._permuteHelper(nums)

print(Solution().permute([1,2,3]))