Determine n related elements with least sum from a matrix?

Question

Consider defining a matrix such as mat:

size = 1000;
rnd = Table[RandomReal[{0, 1}], {i, 1, size}, {j, 1, size}];
mat = rnd + Transpose[rnd] + DiagonalMatrix[Table[100, {i, 1, size}]];

This matrix is symmetric and has off-diagonal entries between 0 and 2. I would like to have a function

res = getLeast[mat,n];

that would return a list of n indices between 1 and size such that

sum = Sum[mat[[ res[[i]] , res[[j]] ]],{i,1,n-1},{j,i+1,n}];

gives the smallest possible sum out of all possible selections of n indices res. Of course one could calculate all possible res and sort the corresponding results for sum by brute force. But perhaps there is a more convenient way to do this in Mathematica? Thanks for any suggestion!

EDIT:

For example, consider the following 6x6 case:

mat = {{101.748, 0.52303, 1.2432, 0.6879, 1.92495, 1.90424}, 
      {0.52303, 100.913, 1.26134, 0.735809, 0.787014, 1.02366}, 
      {1.2432, 1.26134, 101.341, 1.24986, 0.646437, 0.522691}, 
      {0.6879, 0.735809, 1.24986, 101.18, 0.799003, 0.994439}, 
      {1.92495, 0.787014, 0.646437, 0.799003, 100.701, 0.849613}, 
      {1.90424, 1.02366, 0.522691, 0.994439, 0.849613, 101.616}};

for n=3 we can find by brute force that:

n = 3;
subs = Subsets[Table[i, {i, 1, size}], {n}];
nums = Table[
        Sum[mat[[subs[[q, i]], subs[[q, j]]]], {i, 1, n - 1}, {j, i + 1, n}]
       , {q, 1, Length[subs]}];
res = subs[[Position[nums, Min[nums]][[1, 1]]]]

{1, 2, 4}

is the correct set of indices, such that mat[[1,2]]+mat[[1,4]]+mat[[2,4]] is minimal compared to all other sets of 3 indices.