# PBinfo #4485 – divide – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Se dă un șir a1, a2, …, an de numere naturale nenule.

Cerința
Să se împartă elementele șirului în două submulțimi astfel încât diferența în modul dintre sumele elementelor din cele două submulțimi să fie minimă.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi șirul de n numere naturale, separate prin spații.

Date de ieșire
Programul va afișa pe ecran un singur număr natural D, reprezentând diferența în modul dintre sumele elementelor din cele două submulțimi alese.

Restricții și precizări

2 ≤ n ≤ 20
cele n numere din șir vor fi nenule și mai mici decât 1.000.000.000
fiecare număr din șir trebuie să fie într-o singură submulțime

Exemplul 1:
Intrare

5
4 2 7 6 5
Ieșire

0
Explicație
Prima mulțime poate fi {4, 2, 6} și a doua {7, 5}. Sumele sunt 12 și 12 și au diferența 0.

Exemplul 2:
Intrare

5
4 2 7 6 22
Ieșire

3
Explicație
Prima mulțime va fi {4, 2, 7, 6} și a doua {22}. Sumele sunt 19 și 22 și au diferența în modul 3.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int a[25], n, t[25];
int main()
{
    int i, j;
    long long dif, difmin;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> t[i];
    difmin = (1LL << 61);
    a[n] = 1;
    while (a[0] == 0)
    {
        /// calcul diferente:
        dif = 0;
        for (i = 1; i <= n; i++)
            if (a[i] == 0) dif -= t[i];
            else dif += t[i];
        dif = abs(dif);
        difmin = min(difmin, dif);
        for (i = n; a[i] == 1; i--)
            a[i] = 0;
        a[i] = 1;
    }
    cout << difmin;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4485)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4485/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4485/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)