저도 아직 풀지는 못해서 코드에 대해 말씀드리기는 머하지만 질문한 내용에 대해서는 말씀드릴 수 있을 것 같습니다!

코드를 보면 

for (int i = 0; i < 21; i++) {
   v.push_back(b[i]);
   dfs(cnt+1);
   v.pop_back();
}

를 통해서 v에 값을 저장한 후에 dfs를 실행시키는 방식이신 것 같아요.

작성하신 알고리즘은 만약 n값이 4라고 가정한다면 

v[0]에 -10~10안의 값을 넣고

v[1]에 -10~10안의 값을 넣고

v[2]에 -10~10안의 값을 넣고

v[3]에 -10~10안의 값을 넣고

그 후에 조건이 만족하는지 확인하는 것 같습니다. 즉 각 자리수까지의 경우를 먼저 구하고 그 다음 조건이 맞는지 확인하는 방식이신 것 같습니다.맞나요?

하지만 이 경우는 21^4정도의 복잡도를 가지기 때문에 괜찮다 할 수 있지만 10자리의 경우는 21^10이니까 당연히 1억번의 계산정도는 가뿐히 넘지 않을까 싶네요.

말씀하신 조합의 경우로 복잡도를 생각하셨지만 이 내용에는 중복을 허용하지 않는다는 내용이 있지 않습니다. 

즉 -1을 v에 넣었어도 다음 값에 -1이 나올 수 있다는 점을 가정해야할 것 같습니다.

그렇다면 21^n정도의 복잡도를 가진다고 추측을 해볼 수 있겠네요.

이 경우에는 이 점이 핵심인 것 같아요. 

21^n을 피할 수는 없지만 도중에 다음 수가 아니면 바로 계산을 취소하면 불필요한 계산을 줄일 수 있습니다.

예를 들어 

4

- + 0 + + + + - - +

를 입력한 경우

첫번째에 -10을 넣고

그 다음번째에 1을 넣었다면 s[0][1]의 값인 -10+1의 값이 -9이기때문에 뒤의 값이 어떤 값을 넣더라고 이미 두번째인 +조건은 만족하지 않습니다.

즉 그 이후인 s[0][2], s[0][3], s[1][1], s[1][2] 등의 값을 계산할 필요가 없습니다.

이렇게 계산방법을 줄이기 위해 전부 정해지지 않은 상태에서 수들의 합을 구해 조건을 먼저 따지고 수를 넣는것이 계산수를 줄일 수 있고, 시간을 줄일 수 있습니다!