แบ่งอาร์เรย์เป็นสองส่วนที่ผลรวมเท่ากันตามเงื่อนไขเฉพาะ ใน C++

บทนำ

กำหนดอาร์เรย์ arr ต้องการตรวจสอบว่าสามารถแบ่งเป็นสอง sub-array ได้หรือไม่ โดย:

• ผลรวมทั้งสองส่วนเท่ากัน
• จำนวนที่หาร 5 ลงตัว → อยู่กลุ่มซ้าย
• จำนวนที่หาร 3 ลงตัวแต่ไม่ใช่ 5 → อยู่กลุ่มขวา
• จำนวนอื่น → ใส่ได้ทั้งสองกลุ่ม

ตัวอย่าง

arr = {1, 4, 3} → แบ่งได้: {1,3} sum=4 และ {4} sum=4 (3 หาร 3 ลงตัว ไปขวา, 1,4 ใส่ได้ทั้งคู่)

อัลกอริทึม (Recursive Backtracking)

isSplitArray(arr, n, start, left_sum, 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(..., left_sum+arr[start], right_sum) 
                           OR isSplitArray(..., left_sum, right_sum+arr[start])
    return isSplitArray(arr, n, start+1, left_sum, right_sum)

ตัวอย่างโค้ด C++

#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 << "Can be split";
    else
        cout << "Can not be split";
    return 0;
}

ผลลัพธ์

Can be split