[Leetcode] 46. Permutations

🔗 Problem Link

Permutations - LeetCode

---

❔Thinking

• 주어진 숫자들을 모두 활용해 만들 수 있는 수열을 리스트에 담아 반환한다.

---

💻Solution

1. 조합을 활용한 풀이

from itertools import permutations
def permute(self, nums):
    return list(permutations(nums, len(nums)))

 

2. DFS를 활용한 풀이 - 반복문

def permute(self, nums):
    result = []
    n = len(nums)
    stack = [[0, nums, []]]
    while stack:
        length, integers, ans = stack.pop()
        if length == n:
            result.append(ans)
        else:
            for i in range(len(integers)):
                stack.append([length+1, integers[:i]+integers[i+1:], ans+[integers[i]]])
    return result

 

3. DFS를 활용한 풀이 - 재귀

def dfs(self, nums, ans, result):
    if not nums:
        result.append(ans)

    for i in range(len(nums)):
        dfs(nums[:i]+nums[i+1:], ans+[nums[i]], result)
        
def permute(self, nums):
    result = []
    dfs(nums, [], result)
    return result

---

🗝️keypoint

1. 주어진 수를 모두 활용해야 하므로, 현재 수열 list가 주어진 nums와 길이가 같은지 확인한다.
2. nums를 직접 변경할 경우 이후 과정이 불가능하다.