Skip to main content

46. Permutations

https://leetcode.com/problems/permutations/

Python​

Built-in itertools.permutations​

  • 用Python作弊...
  • itertools.permutations可以帶第二個參數r，決定要取的排列長度
from itertools import permutations


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return [perm for perm in permutations(nums)]

Backtracking​

  • 回朔法窮舉
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        used = [False] * len(nums)

        def backtrack(path):
            # Reach leaf, accept the path into result and end the recursive
            if len(path) == len(nums):
                result.append(path[:])  # Copy the List to prevent Copy-by-reference
                return

            # For each options
            for i in range(len(nums)):
                # Ignore the invalid option (used in path)
                if used[i]:
                    continue

                # Make the choice
                path.append(nums[i])
                used[i] = True

                # Go to next level
                backtrack(path)

                # Rollback the choicen
                path.pop()
                used[i] = False

        backtrack([])

        return result