LeetCode 46. Permutations

問題はこちら
難易度はmedium

問題概要

異なる整数の配列 nums が与えられたとき、可能なすべての順列を返す。どのような順序で答えを返してもよい。

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

答え

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(path):
            if len(path) == len(nums):
                result.append(path[:])  # Make a copy of the current permutation
                return
            
            for num in nums:
                if num not in path:
                    path.append(num)  # Add the number to the current permutation
                    backtrack(path)
                    path.pop()  # Backtrack: Remove the last added number
        
        result = []
        backtrack([])
        return result

backtrack()は再帰関数。

pathの中に答えの候補を入れていく。特徴的なのはfor文の最後でpop()を呼び出してその要素を捨てているところ。

今までのbacktrack()と違って問題をさらに小さく簡単に、ではなくpathの中にどんどん入れていき、要素数がnumsと同じになったところで答えに加えている。

今回は例を示さないほどわかりやすくはある。

コード改良

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start):
            if start == len(nums):
                result.append(nums[:])  # Add the current permutation to the result
                return
            
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]  # Swap elements
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]  # Backtrack: Restore the elements
        
        result = []
        backtrack(0)
        return result

先ほどのコードと比べると、

• numsの交換のみで答えの要素を計算しているため、pathの容量分が節約されている。
• リストの中から要素を見つけるという計算量の重い部分がなくなっています。

swapのみでpermutationを表現する手法は他でも使えそうですね。
直感的なコードではないですが。