n(짝수)과 n명의 코인개수를 입력받아 두 팀으로 나누고 두 팀의 코인개수의 최소값을 출력하고자 합니다. 6과 10 20 30 40 30 20을 입력하면 값이 10으로 출력되어야 합니다.

먼저 팀을 나눠야 할 것 같아서 조합으로 다 출력해보았습니다.

'''

public static void main(String[] args) {
    // TODO Auto-generated method stub

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[] s = new int[n];
    int[] bucket = new int[n/2];

    for(int i = 0; i < s.length; i++)
        s[i] = sc.nextInt();

   pick(s, n, bucket, n/2, n/2);
}
public static void pick(int[] item, int itemSize, int[] bucket, int bucketSize, int k)
{//조합

    int i, total = 0, sum = 0;
    int smallest, lastIndex, min = 999999;

    for(i = 0; i < itemSize; i++) {
        total += item[i];
    }

    if ( k == 0 ) // trivial case
    {
        int team = 0;
        for(i = 0; i < bucketSize; i++) {
            System.out.printf("%s ", item[bucket[i]]);
            sum += item[bucket[i]];
        }
        System.out.println(sum);
        return;
    }
    lastIndex = bucketSize - k - 1;

    if(bucketSize == k)
        smallest = 0;
    else
        smallest = bucket[lastIndex]+1;

    for(i = smallest; i < itemSize; i++)
    {
        bucket[lastIndex+1] = i;
        pick( item, itemSize, bucket, bucketSize, k-1 );
    }
}'''

이 코드를 구현하면 n/2명의 코인과 n/2명의 코인의 합의 경우의 수가 출력됩니다.

두 팀의 코인개수의 최소값을 출력하기 위해서는 이 중 하나가 선택되어야 할 텐데 그 부분에서 막혔습니다.

item값의 total을 구해서 sum을 빼면 다른팀의 코인의 합이 나오니 sum과 다른팀의 코인의 합의 차를 구해서 중복되는 값을 제외하고 배열에 넣어 최소값을 구해 반환하면 될 것 같다고 생각했습니다. 그치만 이를 구현하기가 너무 어렵더라구요.

제가 생각한 논리가 잘못된것인지 구현을 못하는 건지 잘 모르겠습니다.

코드를 구현해주실 수 있으시다면 너무 감사드리겠습니다. 방향성을 제시해주셔도 좀 더 생각해보고 다시 풀어보겠습니다. 감사합니다.