[LeetCode] 46. Permutation

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

가능한 모든 순열을 반환합니다

✍️ 풀이

---

1. 내가 풀었던 방법으로 tmp리스트에 매 단계의 선택값을 저장해두고 다음 단계 진행 시 tmp리스트에 없는 값만을 선택하도록 한다.

2. 책에 나와 있는 것처럼 리스트에서 선택한 값을 제외시키면서 진행하는 방법

• 매 진행시마다 선택한 값을 리스트에서 삭제하고 선택 값은 따로 기록해둔다.
• dfs를 빠져나오면 기록한 값을 빼주고 복제한 리스트에서 다시 진행한다.

🛠 코드

---

• code 1

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(index):
            if len(tmp) == len(nums):
                cp = tmp[:] # 파이썬의 객체 참조 특성으로 인해 꼭 복사를 해줘야 한다.d
                result.append(cp)
                return
            for i in range(len(nums)):
                if nums[i] not in tmp:
                    tmp.append(nums[i])
                    dfs(i + 1)
                    tmp.pop()
        result = []
        tmp = []
        dfs(0)
        print(result)
        return result

• code 2

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(elements):
            if len(elements) == 0:
                result.append(prev_elements[:])
            for e in elements:
                next_elements = elements[:]
                next_elements.remove(e)
                
                prev_elements.append(e)
                dfs(next_elements)
                prev_elements.pop()
                
        result = []
        prev_elements = []
        dfs(nums)
        return result
        
            

---

📝 정리

---

🎈 참고

---

Book 링크