Tối ưu bài toán chia dãy thành 2 tập con có tổng bằng nhau

[honghm211 (hoan_h3)]

Cho tập các số A[] = (a1, a2, …, an). Hãy kiểm tra xem ta có thể chia tập A[] thành hai tập con sao cho tổng các phần tử của hai tập con bằng nhau hay không?
Thỏa mãn ràng buộc:1≤N≤100; 1≤ A[i] ≤100.

void bt(int i, int cur) {
	if(cur == sum/2) {
		isS = true;
		return;
	}
	if(cur <= sum/2 && i < n && !isS) {
		for(int j=0; j<=1; j++) {
			bt(i+1, cur + j*a[i]);
		}
	}
}

• Em dùng quay lui nma O(2^n) bị TLE chạy quá 2s, các anh/chi cho em hỏi có cách nào giải bài này tối ưu hơn không ạ? Em cảm ơn

[rogp10]

Tập con: Dùng QHĐ thì độ phức tạp là O(N * (tổng các số dương - tổng các số âm)) và số ô nhớ là O(tổng các số dương - tổng các số âm).

Đại khái là dùng mảng S[k] = tồn tại tập con có tổng bằng k không. S[0] có thể khởi tạo bằng false để không chấp nhận tập rỗng.

[library (La biblioteca)]

Bài này cậu có thể chuyển về việc chọn n/2 số có tổng bằng sum/2 (sum là tổng các phần tử). Nếu việc chọn thành công => chia được, và ngược lại.
Giải thuật chọn n/2 số có tổng bằng sum/2 có thể xem ở đây.
Cậu không cần tìm hết tất cả các bộ số có thể như bài toán này, và worst case scenario giải thuật này có độ phức tạp là O(n^3) (dễ chịu hơn 2^n nếu n lớn).

Hope it helps!

EDIT: oops! đề bài không quan tâm tới số phần tử trong mỗi set.
Tớ không nghĩ giải thuật kể trên hoạt động với dữ kiện đó. Sorry nha

[tntxtnt]

https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews/3jEPRo5PDvx

đây nè :V