Leetcode 46

Permutation

언어: python3

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        
        result = []
        
        def dfs(path:str, count :int):
            if count == len(nums):
                print('current path is:')
                print(path)
                #result.append(path)
                result.append(path[:])
                print('after appending')
                print(result)
            
            else:
                for num in nums:
                    if num not in path:
                        path.append(num)
                        count += 1
                        dfs(path,count)
                        count -= 1
                        path.pop()
            
        path = []
        count = 0
        dfs(path,count)
        return result
            
        
        

주의할 점: 계산한 path를 append 하는 과정에서 path[:] 가 아닌 path로 하게 되면 객체 주소 자체를 추가하게 되므로 나중에 path 값이 바뀌면 따라 바뀌게 된다.

그러므로 path[:] 로 값만 복사할 수 있도록!

두 번째 방법

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)
             dfs(next_elements)
             prev_elements.pop()
             
     dfs(nums)
     return results
     

prev_elements에 이미 추가된 원소들을, next_elements에 다음 permutation 대상이 되는 string을 넣는다

세 번째 방법

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

Built-in 라이브러리를 이용한 방법
단, tuple을 반환하기 때문에 정확한 풀이는 map(list,itertools....) 이 되어야 할 것이다.