Bài tập đếm số cách chia mảng thành n phần sao cho tổng mỗi phần lớn hơn k

[Phuoc_Nguyen3 (Phước Nguyễn)]

Trong một cuộc thi, các thi sinh sẽ được chia thành các đội để đấu với nhau, thông tin của các thí sinh được thể hiện ở mảng arr: thứ sinh thứ i sẽ có số điểm là arr[i]. BTC muốn chia toàn bộ thí sinh thành n đội, sao cho tổng điểm của mỗi đội đều không được bé hơn k. Bạn hãy giúp BTC xem có bao nhiêu cách chia đội hợp lệ.

Ví dụ:

Với arr = [1, 2, 3], n = 2, k = 2 thì splArray(arr, n, k) = 4;

Cách chia đội là:

Đội 1 gồm thí sinh 1, 2 còn đội 2 gồm thí sinh 3.
Đội 1 gồm thí sinh 3 còn đội 2 gồm thí sinh 1, 2.
Đội 1 gồm thí sinh 1, 3 còn đội 2 gồm thí sinh 2.
Đội 1 gồm thí sinh 2 còn đội 2 gồm thí sinh 1, 3.
Đầu vào/Đầu ra:

[Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.

[Đầu vào] Array.Integer arr
1 <= arr.length <= 10
0 <= arr[i] <= 10^5
Integer n, k
1 <= n <= 10
1 <= k <= 10^5

[Đầu ra] Integer
Nhờ mọi người chỉ giúp mình bài này với ạ. Xin cảm ơn

[micache (Huy)]

Mình không chắc lắm nhưng như mình tính thì ra công thức như này
n! * C(q)(d) * C(t - 1)(d - q + t - 1)
với
n : độ dài mảng
q : số đội có số thí sinh = 1
d : số thí sinh có số điểm >= k
t : số đội có số thí sinh >= 2