Chia mảng thành hai phần bằng tổng theo điều kiện trong C++

Cho mảng arr. Kiểm tra có thể chia thành hai nhóm thỏa mãn:

• Tổng hai nhóm bằng nhau.
• Phần tử chia hết cho 5 -> nhóm trái.
• Phần tử chia hết cho 3 (nhưng không chia hết 5) -> nhóm phải.
• Các phần tử còn lại -> có thể đặt nhóm nào cũng được.

Ví dụ: {1, 4, 3} -> chia được: nhóm trái {1,3} tổng 4, nhóm phải {4} tổng 4. (3 chia hết 3 -> phải, 1,4 tự do).

Dùng đệ quy backtracking: duyệt từng phần tử, nếu bắt buộc thì cộng vào nhóm tương ứng, nếu tự do thì thử cả hai nhánh.

Thuật toán

isSplitArray(arr, n, start, left_sum, right_sum):
    Nếu start == n: trả về left_sum == right_sum
    Nếu arr[start] % 5 == 0: left_sum += arr[start]
    Ngược lại nếu arr[start] % 3 == 0: right_sum += arr[start]
    Ngược lại: trả về OR của hai trường hợp thêm vào trái hoặc phải
    Gọi đệ quy start+1

Ví dụ code

#include <iostream>
using namespace std;

bool isSplitArray(int* arr, int n, int start, int left_sum, int right_sum) {
    if (start == n) return left_sum == right_sum;
    if (arr[start] % 5 == 0) left_sum += arr[start];
    else if (arr[start] % 3 == 0) right_sum += arr[start];
    else return isSplitArray(arr, n, start+1, left_sum+arr[start], right_sum) ||
                   isSplitArray(arr, n, start+1, left_sum, right_sum+arr[start]);
    return isSplitArray(arr, n, start+1, left_sum, right_sum);
}

int main() {
    int arr[] = {1, 4, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    if (isSplitArray(arr, n, 0, 0, 0))
        cout << "Co the chia";
    else
        cout << "Khong the chia";
    return 0;
}

Kết quả

Co the chia