[1스4코2파] # 217. LeetCode 46. Permutations

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (217차)
[4코1파] 2023.01.13~ (209일차)
[1스4코1파] 2023.04.12~ (120일차)
[1스4코2파] 2023.05.03 ~ (98일차)

Today :

2023.08.09 [217일차]
backtracking
https://leetcode.com/problems/permutations/

46. Permutations

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

문제 설명

각기 다른 int형 원소로 구성된 배열 nums가 주어졌을 때, 해당 원소의 permutations(조합)을 return 함

문제 풀이 방법

dfs로 내려가면서, nums의 index를 방문 처리하면서 dfs를 돌고
다시 backtracking 하기 위해서 pop 해주고 방문했던 index를 remove 해주면서
dfs 를 진행한다.... (갸어렵네)

내 코드

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        visited = set()

        def dfs(idx, cur):
            if len(cur) == len(nums):
                ans.append(cur.copy())
                return

            for i in range(len(nums)):
                if i not in visited:
                    visited.add(i)
                    cur.append(nums[i])
                    dfs(i,cur)
                    cur.pop()
                    visited.remove(i)

        dfs(0, [])
        return ans

증빙

여담

bfs랑 backtracking은 a4에 그려가면서 풀라고 옆자리 훈장님이 말씀하심