Chia mảng thành K tập con có tổng bằng nhau

[Tuan_Cris (tạch C++)]

các a giúp e thuật toán bài này,e làm khi gửi toàn bị chạy quá time dù dùng đệ quy hay quy hoạch động

[SITUVN.gcd]

• Tính tổng.
• Chia lấy dư và chia nguyên.
• Sẽ có kết quả.

[dtran]

chuẩn luôn, thả tim

[Tuan_Cris (tạch C++)]

ko hiểu ạ,a nói rõ hơn đi

[dtran]

{2, 1, 4, 5, 6}
Tổng là 18
K=1 luôn được
K=2 => 18/2=9 dư 0 => sẽ có khả năng chia dc K tập con với mỗi tập con có tổng =9
K=3 =>18/3=6 dư 0 => sẽ có khả năng chia dc K tập con với mỗi tập con có tổng =6
K=6 => 18/6=3 dư 0 => sẽ có khả năng chia dc K tập con với mỗi tập con có tổng =3 tuy nhiên ở tập trên Max =6 > 3 nên loại.

• Vậy chúng ta chỉ sẽ có khả năng chia với 3 trường hợp K=1,2,3
  Do K=1 luôn được rồi nên ta chỉ xét K=2,3
  Với K=2 thì ta được 2 cặp {2,1,6} {4,5}
  Với K=3 thì ta được 3 cặp {2,4} {5,1} {6}

[rogp10]

Bước đầu thôi.

Sau khi có tổng cần tìm, ta đệ quy theo cả N và K với bảng chọn. Số ko âm thì nhánh cận cực dễ.