Permutations (in Python)

Problem

Given a collection of distinct integers, return all possible permutations.

Example:

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

Solution

•종료 조건 : index가 현재 배열의 길이와 같을 때.

•i번째 원소와 현재 선택한 원소(first)를 바꾸고

•i+1번째 원소부터 다시 탐색을 시작한다.

•i번째 원소를 다시 돌려 놓는다. (다음 탐색에 영향을 주지 않기 위해서.)

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums :
            return []
 
        ans = []
        n = len(nums)
 
        def backtrack(first=0) :
 
            if first == n :
                ans.append(nums[:])
            for i in range(first, n) :
                
                nums[i], nums[first] = nums[first], nums[i]
                backtrack(first+1)
                nums[i], nums[first] = nums[first], nums[i]
        
        backtrack()
        return ans

Complexity Analysis

• Time complexity : \(O(N!)\) to build N! solutions.

•Space complexity : \(O(N!)\) since one has to keep N! solutions.

Source

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