[LeetCode] 순열

https://leetcode.com/problems/permutations/

Permutations - LeetCode

문제해설:

사용자가 리스트를 입력하면 순열을 구하는 문제이다.

[1,2,3]을 받았다면 이것을 이용해 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] 총 6개의 값이 나온다.

 

---

<스택 구현>

• 스택이 처음에 존재하지 않는다면 스택을 초기화 해준다.

	if stack is None:
                stack = []

* 종료조건 stack 과 받아온 리스트의 길이가 같으면 output에 추가해주고 return 해 그 전의 자리로 돌아간다.

	if len(stack) == len(nums):
                output.append(stack)
                return

* nums 반복문을 돌려주며 stack에 w가 존재하지 않는다면 재귀적으로 dfs을 호출해준다.

            for w in nums:
                if w not in stack:
                    dfs(stack + [w])

 

---

class Solution:
    def permute_stack(self, nums):
        def dfs(stack=None):
            if stack is None:
                stack = []
            if len(stack) == len(nums):
                output.append(stack)
                return
            for w in nums:
                if w not in stack:
                    dfs(stack + [w])
            print("output = ", output)
        output = []
        dfs()
        return output