@ZhassanB You can avoid the random sampling if you use a more systematic approach.

The idea is to first transform the transactions into an array of debts, we only care about the net positive or negative amount for each person, we don't even care which person owes what. Once this is complied into an array, discard the zeros, those will obviously take zero transfers to balance.

Then enter into a loop asking, can I find 2 numbers that will cancel each other out, because in this case 1 transfer can remove these 2 people from the set and we cannot do any better than 1 transfer to remove 2 people. If a set that contains 2 numbers and sums to zero is found, remove those 2 numbers and count that as 1 transfer. Repeat this as long as you can remove sets of length 2 you are performing the minimum number of transfers.

Once you have exhausted finding sets of 2 that sum to zero move to finding sets of 3 that sum to zero, because you now cannot do any better than clearing 3 people with 2 transfers. Repeat until it is necessary to move to sets of size 4 where you'll need 3 transactions to remove 4 people. And repeat, we know that to remove a set of size N which cannot be removed in sub sets we will need N-1 transfers.

Eventually you will remove all the numbers and you are done, and we know we will find a solution because the entire array sums to zero.

public int MinTransfers(int[,] transactions)
{
// convert the transactions to a balance count for each person
Dictionary<int, int> map = new Dictionary<int, int>();
for (int i = 0; i < transactions.GetLength(0); i++)
{
if (!map.ContainsKey(transactions[i, 0])) map[transactions[i, 0]] = 0;
if (!map.ContainsKey(transactions[i, 1])) map[transactions[i, 1]] = 0;
map[transactions[i, 0]] += transactions[i, 2];
map[transactions[i, 1]] -= transactions[i, 2];
}
// take the non-zero balances and sort them into an array
// the sorting will help with DFS pruning
List<int> nums = map.Values.Where(x => x != 0).OrderBy(x => x).ToList();
int cnt = 0;
int targetLen = 2;
while (nums.Count > 0)
{
// try to find a set of length = targetLen which sum to 0
List<int> indexes = new List<int>();
bool found = Find(nums, indexes, targetLen, 0, 0);
if (found)
{
// because this is the minimum length set that can sum to zero,
// this set will require (len - 1) transactions to balance
cnt += indexes.Count - 1;
// remove these values from the list and try again for another set of this length
int indexesIndex = 0;
List<int> next = new List<int>();
for (int i = 0; i < nums.Count; i++)
{
if (indexesIndex < indexes.Count && i == indexes[indexesIndex]) indexesIndex++;
else next.Add(nums[i]);
}
nums = next;
}
else
{
// no set of this length was found, try the next length
targetLen++;
}
}
return cnt;
}
// DFS - find targetLen amount of items that sum to zero
// store the indexes of these elements
public bool Find(List<int> nums, List<int> indexes, int targetLen, int sum, int index)
{
if (sum > 0) return false; // pruning - array is sorted
if (indexes.Count == targetLen && sum == 0) return true;
if (indexes.Count == targetLen && sum != 0) return false;
if (nums.Count - index < targetLen - indexes.Count) return false;
for (int i = index; i < nums.Count; i++)
{
indexes.Add(i);
if (Find(nums, indexes, targetLen, sum + nums[i], i + 1))
{
return true;
}
indexes.RemoveAt(indexes.Count - 1);
}
return false;
}