[LeetCode] Permutations

문제 이동
난이도: ⭐️⭐️

첫 번째 제출

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def permutate(nums, res):
            if len(nums) == 1:
                results.append(res + [nums[0]])
                return

            for i in range(len(nums)):
                permutate(nums[:i]+nums[i+1:], res + [nums[i]])
        
        results = []
        permutate(nums, [])

        return results

예전에 삼성 코테 볼 때 itertools 못 써서 공부했던 기억이 있어서 어케 풀었다.
원리는 단순.

permute([1,2,3,4]) 
= [1, permute(2,3,4)] + [2, permute(1,3,4)] + [3, permute(1,2,4)] + [4, permute(1,2,3)]
= [1, 2, permute(3,4)] + [1, 3, permute(2,4)] + ...
= [1, 2, 3, permute(4)] + [1, 2, 4, permute(3)] + ...

하나씩 앞에 넣는 식으로 하다가 남는 게 1개 이하면 종료

근데 이거 막상 실전에서는 머리 쥐어짤 듯ㅋ

어쨌든 for문 안에 permutate 재귀할 때 res + [nums[i]] 한 것처럼 새로 들어가야 함. res 변수의 값을 아예 바꿔서 들어가면 안됨. 그럼 depth 들어가면서 res 값이 바뀌어서 다시 1층으로 나와도 res가 바뀐 값이라 누적되는 식이 됨.