순열 알고리즘 2. 가능한 모든 순열 찾기

                                    ⚠️ n : 1..6

✅ next permutations에서 사용한 알고리즘을 전체 적을 사용한다.
>>> 역으로 조회하여 처음으로 감소되는 구간을 찾고
    >>> pivot
>>> 그 위치로부터 가장 큰 값을 찾아서 바꿔주고
>>> pivot 이후부터 reverse() 해준다.

                                    class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []

        def find_next(arr):
            n = len(arr)
            pivot = 99999

            # set pivot
            for i in range(n- 1, 0, -1):
                if arr[i-1] < arr[i]:
                    pivot = arr[i-1]

            # if pivot = 99999
            # means end !
            if pivot == 99999:
                return [-100]

            #find next value ⌚O(n)
            next_min = 999999
            target_idx = 99999
            for i in range(pivot + 1, n):
                next_min = min(next_min, arr[i])

            if target_idx == 99999:
                target_idx = n - 1

            # swap
            arr[pivot], arr[target_idx] = arr[target_idx], arr[pivot]

            # reverse idx > pivot
            start = pivot + 1
            end = n - 1
            while start <= end: ⌚O(n)
                arr[start] = arr[end]
                start += 1
                end -= 1

            return arr

        while 1:
            next_per = find_next(nums)
            result.append(next_per)
            if next_per == [-100]: ⌚ exponential ❌❌ ➡️ Factorial!
                break

        return result

                                    🤔 그냥 n!로 구현해보자.

                                    🖊️ 논리를 수정하자

✅ DFS로 dictioanry와 arr를 넘겨주어 크기가 n이 되는 순간 return한다.

✅ 모든 순간에서 dictioanry를 참고하여 가능한 모든 후보들을 하나씩 넣는다.

                                    import copy
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []

        def dfs(comb, candidate): # []. {}
            if len(comb) == len(nums):
                result.append(comb)
                return

            for key in candidate:
                if candidate[key] == 0:
                    continue
                tmp = comb[::]
                tmp.append(key)

                c_candidate = copy.copy(candidate)
                c_candidate[key] = 0

                dfs(tmp, c_candidate)

        first_candidate = {}
        for num in nums:
            first_candidate[num] = 1

        dfs([], first_candidate)
        return result

                                    🤔 효율성을 개선하기 위해 어떻게 해야할까
>>> 근데 개선해도 n!이 최선이긴하고, 디테일한 부분이 개선될 가능성이 크다.
    >>> 예를들어 배열복사, dictioanry 복사 로직 등이 개선될 수 있을 것이다.