[백준 14889] 스타트와 링크 (조합) (C/C++)

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
 
int N;
int relation[25][25];
vector<int> start_candidate;
int Min = 99999999;
 
void combination(int idx, int cnt)
{
    if(cnt == N/2)
    {
        int start = 0;
        int link = 0;
        vector<int> link_candidate;
        int visited[25] = {0};
        
        for(int i = 0; i < start_candidate.size(); i++)
        {
            for(int j = 0; j < start_candidate.size(); j++)
            {
                if(i == j)
                {
                    continue;
                }
                
                start += relation[start_candidate[i]][start_candidate[j]];
            }
        }
        
        for(int i = 0; i < start_candidate.size(); i++)
        {
            visited[start_candidate[i]] = 1;    
        }
        
        for(int i = 1; i <= N; i++)
        {
            if(visited[i] == 0)
            {
                link_candidate.push_back(i);
            }
        }
        
        for(int i = 0; i < link_candidate.size(); i++)
        {
            for(int j = 0; j < link_candidate.size(); j++)
            {
                if(i == j)
                {
                    continue;
                }
                
                link += relation[link_candidate[i]][link_candidate[j]];
            }
        }
        
        if(Min > abs(start-link))
        {
            Min = abs(start-link);
        }
        
        return;
    }
    
    for(int i = idx; i <= N; i++)
    {
        start_candidate.push_back(i);
        combination(i+1, cnt+1);
        start_candidate.pop_back();
    }
}
 
int main(void)
{
//    freopen("B14889_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            cin >> relation[i][j];
        }
    }
    
    combination(1, 0);
    
    cout << Min;
    
    return 0;
}