Submission

PPPPPPPPPP

Score: 100

User: pxsit

Problemset: ประลอง

Language: cpp

Time: 0.001 second

Submitted On: 2024-11-14 21:22:08

#include <stdio.h>
#include <stdlib.h>

int minDiff = 1000000;
int bestSet1[100], bestSet2[100];
int bestSize1, bestSize2;

void findBestSplit(int arr[], int n, int currentIndex, int set1[], int set2[], int size1, int size2, int sum1, int sum2) {
    if (currentIndex == n) {
        if ((size1 == n / 2 && size2 == n / 2) || (size1 == n / 2 + 1 && size2 == n / 2)) {
            int diff = abs(sum1 - sum2);
            if (diff < minDiff) {
                minDiff = diff;
                // Store the best configuration
                bestSize1 = size1;
                bestSize2 = size2;
                for (int i = 0; i < size1; i++)
                    bestSet1[i] = set1[i];
                for (int i = 0; i < size2; i++)
                    bestSet2[i] = set2[i];
            }
        }
        return;
    }

    if (size1 < n / 2 + 1) {
        set1[size1] = arr[currentIndex];
        findBestSplit(arr, n, currentIndex + 1, set1, set2, size1 + 1, size2, sum1 + arr[currentIndex], sum2);
    }

    if (size2 < n / 2) {
        set2[size2] = arr[currentIndex];
        findBestSplit(arr, n, currentIndex + 1, set1, set2, size1, size2 + 1, sum1, sum2 + arr[currentIndex]);
    }
}

int main() {
    int n;
    scanf("%d", &n);

    int arr[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    int set1[n], set2[n];
    findBestSplit(arr, n, 0, set1, set2, 0, 0, 0, 0);

    // Print only the best configuration
    for (int i = 0; i < bestSize2; i++) {
        printf("%d", bestSet2[i]);
        if (i < bestSize2 - 1) printf(" ");
    }
    printf("\n");
    for (int i = 0; i < bestSize1; i++) {
        printf("%d", bestSet1[i]);
        if (i < bestSize1 - 1) printf(" ");
    }

    return 0;
}