leetcode : Permutations [backtracking] 모든 순열 찾기

https://leetcode.com/problems/permutations

Permutations - LeetCode

 

전형적인 Backtracking (속칭 노가다) 문제다.

리스트를 줄테니까 해당 리스트의 요소들을 나열하는 모든 경우의 수를 다 구해서 리턴하라는 것이다.

 

나는 아주 직관적이고 단순하게 풀었다.

1. 남은 요소 중에 하나 택해서 임시리스트에 넣는다.

2. 반복한다.

3. 남은 요소가 없으면 임시리스트를 정답 리스트에 추가한다.

 

 

아 이게 말로 쓰려니까 쉽지가 않네

DFS로 푼거다.

 

슈도코드를 먼저보자

    def func(self, 임시리스트, 정답리스트, nums, check):

        반복문 : i를 0부터 nums길이-1까지 돌린다
            nums[i]가 임시리스트에 없으면:
                임시리스트의 맨끝에 nums[i]를 넣는다
                재귀호출(임시리스트, 정답리스트, nums, check)
                임시리스트의 맨끝에있는 num[i]를 뺀다.
                
        다 체크되어 있으면:

            정답리스트에 임시리스트를 추가한다

굵은 글씨 친 부분이 핵심이다.

1. 넣고 2. 재귀호출 3. 빼고

 

 

class Solution:
    def helper(self, tmp, ans, nums, check):
        
        all_checked = True
        for i in range(len(nums)):
            if check[i] == False:
                all_checked = False
                check[i] = True
                tmp.append(nums[i])
                self.helper(tmp, ans, nums, check)
                check[i] = False
                tmp.pop()
                
        if all_checked:
            ans.append(tmp[:])
    
    def permute(self, nums: List[int]) -> List[List[int]]:
        check = [False] * len(nums)
        ans = []
        
        self.helper([], ans, nums, check)
        
        return ans

 

변수 설명

nums : 입력 리스트

check : 배열의 각 요소가 tmp 배열에 있는지 없는지를 체크하기 위한 boolean 리스트

ans : 마지막에 리턴할 정답 리스트

tmp : 임시 리스트

 

메모리 usage는 만-족.

시간은.. 흠.. 50%? 불만-족...

좀만 더 최적화 해보고싶다.

나중에 해야지