N개의 숫자구성을 완성해나가는 과정에서 매번 좋은 수열인지 나쁜 수열인지 O(N^2)에 검사할 수 있으니까 완전탐색으로 풀어도 된다고 생각합니다.

이론적인 답변은 못 드리겠고 실험만 해봤는데, 실제로 backtracking이 거의 일어나지 않습니다. n=5000일 때 재귀함수 call이 5500번도 안 일어납니다. n=5000이라도 TLE가 안 뜰 겁니다. 2^n개의 status가 있지만 거의 대부분은 가지치기가 되는 거 같습니다.