Ta sử dụng đệ quy quay lui để thử từng trường hợp.
Với mỗi số i từ 1 tới N, ta thử cả hai trường hợp dấu cộng và trừ. Trong 2^N trường hợp, ta xem có trường hợp nào tổng bằng N hay không.
Độ phức tạp cho mỗi testcase: O(2^n)
Tuy nhiên, vì T \leq 1000, nên không thể nào chạy đệ quy với mỗi test, vì trong trường hợp tệ nhất sẽ tốn khoảng 1000 × 2^{20} ≈ 10^9 phép tính.
Vì vậy, ta tính trước đáp án của toàn bộ các N từ 1 tới 20 và lưu lại, khi cần hỏi thì chỉ cần trả lời.
Độ phức tạp tổng: O(2^1 + 2^2 + ··· + 2^k) = O(2^{k+1}), (k \leq 20)
Ta gọi f (N, sum) = 0/1 là khả năng tạo được tổng sum từ N số, 0/1 là không/có.
Ta nhận thấy, nếu f (N, sum) = 1 thì f (N +1, sum +(N +1)) = 1 và f (N +1, sum −(N +1)) = 1.
Vì thế, ta đặt trường hợp ban đầu là f (0, 0) = 1, tức không có số nào và tổng bằng 0, sau đó loang ra các trường hợp khác.
Một lần nữa, vì số lượng testcase lớn, nên ta lưu lại mảng quy hoạch động này rồi khi cần thì truy cập lấy đáp án.
Vì tổng có thể âm nên khi cài đặt, ta có thể cộng toàn bộ các chỉ số tổng cho một lượng (tốt nhất là cộng cho \frac{N(N+1)}{2})
Độ phức tạp: O(N^3), vì tổng của N số xấp xỉ N^2.
Ta nhận thấy, các tổng có thể tạo được qua biến đổi dãy N số đều có cùng tính chẵn lẻ.
Để chứng minh, ta xét tổng X_N = 1 + 2 + 3 + ···+ N . Mỗi lần thay một số i từ dấu cộng thành dấu trừ, tổng giảm đi 2 \times i, tức là giảm đi một lượng là số chẵn. Vì thế tính chẵn lẻ đều không thay đổi, dù có thực hiện bao nhiêu phép biến đổi đi chăng nữa.
Vì vậy với mỗi truy vấn (N, S), ta kiểm tra hai điều kiện −X_N \leq S \leq X_N và S cùng tính chẵn lẻ với X_N hay không. Nếu cả hai đều thỏa mãn thì in ra YES.