CSES 1. Apple Division (1623)

출처: https://cses.fi/problemset/task/1623

---

문제 설명

There are n apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

입력

The first input line has an integer n: the number of apples.

The next line has n integers p_1,p_2,…,p_n: the weight of each apple.

출력

Print one integer: the minimum difference between the weights of the groups.

입력 예

5
3 2 7 4 1

출력 예

1

제약조건

• 1 <= n <= 20
• 1 <= p_i <= 10^9

---

문제 풀이

입력받은 사과들을 양쪽에 각각 넣어보고 무게 차의 최소 값을 찾는다.

프로그램 내용

long ans = 1e18;

void search_diff(int a, long b, vector<int> weight)
{
    if (a == weight.size()) {
        ans = min(ans, abs(b));
        return;
    }
    search_diff(a+1,b+weight[a], weight);	/// add apple to side A
    search_diff(a+1,b-weight[a], weight);	/// add apple to side B
}

int main()
{
    int N;		/// number of apple

    vector<int> weight(N,0);
    for(int idx=0; idx<N ; ++idx)
        cin >> weight[idx];

    search_diff(0,0, weight);

    cout << ans << endl;

 

Introductory problems ( link )