class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        dp = [0 for _ in range(2*n - 1)]
        visit = [0 for _ in range(n + 1)]
        def backtrack(depth, dp, visit):
            if visit[0]:
                return
            if sum(visit) == n and visit[0] == 0:
                visit[0] = 1
                return
            if dp[depth] != 0:
                while dp[depth] != 0:
                    depth += 1
                backtrack(depth, dp, visit)
                if visit[0]:
                    return
            for i in range(n, 1, -1):
                if visit[i] == 0 and depth + i < 2*n - 1 and dp[depth + i] == 0:
                    dp[depth] = i
                    dp[depth + i] = i
                    visit[i] = 1
                    backtrack(depth + 1, dp, visit)
                    if visit[0]:
                        return
                    dp[depth] = 0
                    dp[depth + i] = 0
                    visit[i] = 0
            if visit[1] == 0:
                dp[depth] = 1
                visit[1] = 1
                backtrack(depth + 1, dp, visit)
                if visit[0]:
                    return
                dp[depth] = 0
                visit[1] = 0
            return
        backtrack(0, dp, visit)
        return dp


백트래킹이 정해는 맞는거 같긴 함.

근데 진짜 아무 계획을 안 세우고 고치고 고치고 했더니 코드는 걸레짝이네;