[ALGO] 리트코드 - 순열
리트코드 - 순열
과정
- dfs로 푼 근거는? -> 순열은 가능한 모든 경우의 수를 그래프 형태로 나열한 결과라 할 수 있다.
- 재귀로 푼 근거는? -> 입력이 [1, 2, 3]로 주어졌을 때 [1, 2, 3]을 한번에 풀지 않고 [1], [2], [3]으로 작게 나누어 해결하기 위해서 재귀 사용.
재귀함수
- 자기 자신을 호출/재참조하는 함수이다.
- 주어진 문제를 똑같은 유형의 하위 문제로 나누어 해결한다.
- 어떤 조건(base case)을 마주칠 때까지 자기 자신을 호출한다.
- 복잡한 입력을 더 간단한 입력으로 분류하여 자기 자신을 호출 (recursion case)
풀이
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
prev_elements = []
def dfs(elements):
# base case: 마지막 숫자인 경우 end
if len(elements) == 0:
result.append(prev_elements[:])
# recursion case: 복잡한 입력을 간단하게 바꾸자
for i in elements:
next_elements = elements[:]
next_elements.remove(i)
prev_elements.append(i)
dfs(next_elements)
prev_elements.pop()
dfs(nums)
return result
reference
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
prev_elements = []
def dfs(elements):
# base case: 마지막 숫자인 경우 end
if len(elements) == 0:
result.append(prev_elements[:])
# recursion case: 복잡한 입력을 간단하게 바꾸자
for i in elements:
next_elements = elements[:]
next_elements.remove(i)
prev_elements.append(i)
dfs(next_elements)
prev_elements.pop()
dfs(nums)
return result
Author And Source
이 문제에 관하여([ALGO] 리트코드 - 순열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sqaurelu/ALGO-리트코드-순열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)