Target Sum

Duyệt các số từ trái sang phải, giữ tổng đang tính, rồi rẽ nhánh hai lần tại mỗi số: cộng hoặc trừ số đó. Khi mọi số đều có dấu, đếm 1 nếu tổng bằng target. Mỗi lựa chọn dấu tương ứng với đúng một đường đi, vì vậy cộng các số đếm lại sẽ ra đáp án.

Mỗi lựa chọn tạo ra một nút lá: 2^20 ≈ 10^6 nút lá với 20 số, và mỗi số thêm vào sẽ làm khối lượng công việc tăng gấp đôi.

count(i, total) chỉ phụ thuộc vào i và total, không phụ thuộc vào các dấu đã tạo ra tổng đó. Với nums = [1, 1, 1, 1], các tiền tố +1 -1 và -1 +1 đều đạt tổng 0 tại vị trí 2, nên tìm kiếm từ đó giống nhau. Hãy lưu mỗi kết quả ngay lần đầu tiên và dùng lại.

Tổng đang tính luôn nằm trong khoảng từ -S đến S, nên hãy dịch tổng đi S để dùng làm chỉ số: memo[i][total + S]. Có nhiều nhất n × (2S+1) trạng thái, khoảng 4 × 10^4 với 20 số có tổng là 1000, mỗi trạng thái chỉ cần một lượng thao tác không đổi.

Gọi P là tổng các số mang dấu cộng và N là tổng các số còn lại. Khi đó P - N = target và P + N = S, nên 2P = S + target. Một cách chọn dấu hợp lệ khi và chỉ khi nhóm mang dấu cộng có tổng bằng (S + target) / 2, và mỗi tập con như vậy tương ứng với một cách chọn dấu.

ways[s] đếm số tập con của các số đã xét có tổng bằng s, bắt đầu với ways[0] = 1. Với mỗi số x, một tập con có tổng bằng s có thể bỏ qua x hoặc thêm số đó vào một tập con có tổng bằng s - x. Duyệt s từ lớn xuống nhỏ, để ways[s - x] vẫn giữ giá trị trước khi xét x và không số nào được dùng hai lần. Một số 0 cộng mỗi mục vào chính nó, nhân đôi mọi số đếm: tương ứng với hai cách chọn dấu cho số 0. Đó là n × goal phép cộng, nhiều nhất là 2 × 10^4.