46. Permutations

Permutations - LeetCode

1. 전형적인 DFS

from typing import *
from copy import deepcopy


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        answer = []
        visited = [0] * len(nums)

        def sol(permu_list, visited_list):
            if len(permu_list) == len(nums):
                answer.append(permu_list)
                return
            else:
                for i in range(len(nums)):
                    if not visited_list[i]:
                        new_list = deepcopy(permu_list)
                        new_list.append(nums[i])
                        visited_list[i] = 1
                        sol(new_list, visited_list)
                        visited_list[i] = 0

        sol([], visited)
        return answer

 

2. 아직도 이해하지 못한 DFS

class Solution:
    def permute(self, nums):
        def backtrack(start, end):
            # print(start, end)
            if start == end:
                ans.append(nums[:])
                print(nums[:])
            for i in range(start, end):
                # print(start, i, end)
                nums[start], nums[i] = nums[i], nums[start]
                # print(f"{start} {i} {end} 진입")
                backtrack(start + 1, end)
                # print(f"{start} {i} {end} 탈출")
                nums[start], nums[i] = nums[i], nums[start]
        ans = []
        backtrack(0, len(nums))
        return ans