46. Permutations

Category	ps/bfs & dfs
Tag	bfs & dfs
Tags	permutaiton
난이도	★
발행 여부
사이트	Leet code
실수 유형
이해	완벽히 이해
최종 편집 일시	@2021년 11월 26일 오후 10:08
푼 날짜	@2021년 11월 25일 오후 10:49

문제 해설 및 주의사항

원문

번역 및 주의사항

풀이

내 풀이 코드 (brute force)

풀이 코드 (dfs)

풀이 코드 (itertools)

풀이 코드 (Discuss 에 있던 거)

퇴고

문제 해설 및 주의사항

원문

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

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

번역 및 주의사항

가능한 모든 순열을 return 해라.

Constraints:

• 1 <= nums.length <= 6

• 10 <= nums[i] <= 10

• All the integers of nums are unique.

---

풀이

• dfs 와 brute force 두 가지로 풀어보았다.
  • dfs 는 시간이 오래 걸리고, 공간을 적게 사용했다.
  • brute force 는 빠르고, 공간을 많이 사용했다.

내 풀이 코드 (brute force)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        is_used = {i : False for i in range(-10, 11)}
        def brute_force(index, current_list):
            # If, index is reached limit
            if index == len(nums):
                ans.append(current_list[:])
                return
            
            else:
                for i in nums:
                    if is_used[i]:
                        continue
                    else:
                        is_used[i] = True
                        current_list.append(i)
                        brute_force(index + 1, current_list)
                        is_used[i] = False
                        current_list.pop()
                        
        brute_force(0, [])
        return ans

풀이 코드 (dfs)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        comp_elements = []
        
        def dfs(elements) :
            # If, Leaf node
            if len(elements) == 0:
                ans.append(comp_elements[:])
            
            else:
                for e in elements:
                    next_elements = elements[:]
                    next_elements.remove(e)
                    
                    comp_elements.append(e)
                    dfs(next_elements)
                    comp_elements.pop()
        
        dfs(nums)
        return ans

풀이 코드 (itertools)

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

풀이 코드 (Discuss 에 있던 거)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def dfs(current_nums, current_list):
            if not current_nums:
                ans.append(current_list[:])
                return
            else:
                for i, num in enumerate(current_nums):
                    dfs(current_nums[:i] + current_nums[i+1:], current_list + [num])
                    
        dfs(nums, [])
        return ans

---

퇴고

• 왜 itertools 를 사용한 것 보다 brute force 방식이 더 적은 runtime 성능을 보여주는 것인가..