y-log

46. Permutations

🕵️‍♀️ Question

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

2:

Input: nums = [0,1]

Output: [[0,1],[1,0]]

3:

Input: nums = [1]

Output: [[1]]

📌 Constraints

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

🙋‍♀️ 풀어보자~

서로 다른 정수를 입력받아 가능한 모든 수열을 리턴하는 간단한 순열 문제다.

두가지의 풀이가 존재한다.

version1 : DFS를 활용한 순열 생성

백트래킹(backtracking)이란? :

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다.

최적화 문제와 결정 문제를 푸는 방법이 됩니다.

순열이란 모든 가능한 경우를 그래프 형태로 나열한 결과이다. -> 그래프로 표현 가능하다.

# Runtime: 69 ms
# Memory Usage: 14.4 MB

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        prev_elements = []
        
        def dfs(elements) :
            #리프노드일때
            if len(elements) == 0 :
                results.append(prev_elements[:])
                
            #순열 생성 재귀 호출
            for e in elements:
                next_elements = elements[:]
                next_elements.remove(e)
               
                prev_elements.append(e)
                # print("perv",prev_elements)
                # print("next재귀돌러가즈아",next_elements)
                dfs(next_elements)
                prev_elements.pop()
                # print("**백트래킹",prev_elements)
    
        dfs(nums) 
        return results

# input이 [1,2,3] 면 나오는 출력,,,
perv [1]
next재귀돌러가즈아 [2, 3]
perv [1, 2]
next재귀돌러가즈아 [3]
perv [1, 2, 3]
next재귀돌러가즈아 []
**백트래킹 [1, 2]
**백트래킹 [1]
perv [1, 3]
next재귀돌러가즈아 [2]
perv [1, 3, 2]
next재귀돌러가즈아 []
**백트래킹 [1, 3]
**백트래킹 [1]
**백트래킹 []
perv [2]
next재귀돌러가즈아 [1, 3]
perv [2, 1]
next재귀돌러가즈아 [3]
perv [2, 1, 3]
next재귀돌러가즈아 []
**백트래킹 [2, 1]
**백트래킹 [2]
perv [2, 3]
next재귀돌러가즈아 [1]
perv [2, 3, 1]
next재귀돌러가즈아 []
**백트래킹 [2, 3]
**백트래킹 [2]
**백트래킹 []
perv [3]
next재귀돌러가즈아 [1, 2]
perv [3, 1]
next재귀돌러가즈아 [2]
perv [3, 1, 2]
next재귀돌러가즈아 []
**백트래킹 [3, 1]
**백트래킹 [3]
perv [3, 2]
next재귀돌러가즈아 [1]
perv [3, 2, 1]
next재귀돌러가즈아 []
**백트래킹 [3, 2]
**백트래킹 [3]
**백트래킹 []
=========
perv [0]
next재귀돌러가즈아 [1]
perv [0, 1]
next재귀돌러가즈아 []
**백트래킹 [0]
**백트래킹 []
perv [1]
next재귀돌러가즈아 [0]
perv [1, 0]
next재귀돌러가즈아 []
**백트래킹 [1]
**백트래킹 []

version2. 파이썬의 itertools 모듈을 사용한다.

itertools 
반복자 생성에 최적화된 효율적인 기능들을 제공.
이미 잘 구현된 라이브러리라 버그 발생 가능성이 낮고 효율적으로 설계된 C 라이브러리라 속도도 빠름
📍 사용할 때 주석으로 "# 구현의 효율성, 성능을 위해 사용했다" 라고 달아주면 쵝오~

permutation( ) 함수가 튜플 모음을 반환하기 때문에 리트코드 문제에서는 리스트를 반환하도록 요구하기 때문에 변환처리를 해줘야한다.

# Runtime: 28 ms
# Memory Usage: 14.3 MB

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        import itertools
        return list(map(list, itertools.permutations(nums)))