Nhờ giúp đỡ full test bài tập đếm phương án lựa chọn các phần tử

[Wipad]

Đề bài: Cho n phần tử và số nguyên dương k, hãy tìm xem trong dãy đó có bao nhiêu phương án lựa chọn các phần tử sao cho tổng các phần tử đó đúng bằng k. Biết rằng các cách lựa chọn là hoán vị của nhau thì chỉ tính 1 cách và trong mỗi cách lựa chọn 1 phần tử không được chọn quá 1 lần.

• Input
  Dòng 1: Nhập vào 2 số nguyên dương n và k (n <= 5000, k <= 10^9);
  Dòng 2: Nhập vào n số nguyên a1, a2, …, an (0 <= a[i] <= 10^9);

• Output
  Ghi ra 1 số nguyên là số dư của kết quả tìm được chia cho 123456789.

• Ràng buộc
  Có 40% số test tương ứng với 40% số điểm thỏa mãn điều kiện n <= 20;
  Có 40% số test tương ứng với 40% số điểm thỏa mãn điều kiện 20 < n <= 40;
  Có 20% số test tương ứng với 20% số điểm còn lại có a[i] = i, k = n, n <= 5000.

Input
4 5
4 2 1 3

Output
2

Giải thích:
Cách 1: Lựa chọn phần tử thứ 1 và 3
Cách 2: Lựa chọn phần tử thứ 2 và 4

Nhờ mọi người giúp em subtask 2 với ạ, bài này mặc dù em đã sử dụng cách chia đôi tập hợp nhưng vẫn chỉ được 70% điểm thôi (Subtask 1 và Subtask 3 full điểm rồi ạ), với n > 26 là bị TLE, nhờ mọi người đóng góp ý tưởng. Em cảm ơn.

Code của em: https://ideone.com/lN2YSP

Đây là 1 test bị TLE

Input
29 432848760
18540521 6231505 47673444 43771452 15369503 16692981 49537041 44079168 45522931 24727484 8055287 13669114 40660444 46058848 47245187 24847835 11701156 36459182 16398195 33034551 46353007 14693862 36639646 10277084 29864541 15653844 16171415 25515836 4368252
Output
4

[anonymous273]

bài này bạn xài backtracking brute-force mọi kết quả với đpt O(2^n) nên bị TLE

bạn nên tham khảo về việc sư dụng dynamic programming.

Count of subsets with sum equal to X - GeeksforGeeks

đọc lại thì thấy K quá lớn để có thể xài dp

Update
Có 40% số test tương ứng với 40% số điểm thỏa mãn điều kiện n <= 20 -> DFS
Có 40% số test tương ứng với 40% số điểm thỏa mãn điều kiện 20 < n <= 40 -> DFS
Có 40% số test tương ứng với 40% số điểm còn lại có a[i] = i, k = n, n <= 5000 -> Dynamic programming (link ở trên)

[Wipad]

Anh giải thích về cái DFS rõ hơn được không, em học DFS rồi nhưng không biết áp dụng vào bài này như nào cả

[rogp10]

Quay lui chính là DFS.

[Wipad]

Như em nói ở trên thì subtask 2 với 20 < n <= 40 thì quay lui thông thường không được, em có dùng cách chia tập hợp nhưng vẫn không hết test, bị TLE hết, không biết ngoài việc chia tập hợp ra thì có phải thêm bước nào không anh nhỉ ?

[anonymous273]

vấn đề nằm ở phần in ra kết quả.
chứ code backtrack perf chạy nhanh.

[Wipad]

Với test TLE trên, chỉ chạy mỗi phần quay lui đã mất hơn 11s rồi @@

[anonymous277]

Không biết bạn có gì chứng minh con số 11s kia không? Chứ mình chạy code của bạn ở đây thì kết quả chưa tới 0.5s nữa:

[Wipad]

À không, giống như bác trên nói á, do tìm kết quả lâu quá. Cảm ơn bạn