private Dictionary<string, int> gQualDict = new Dictionary<string, int>();

class qualityWithStatus {
    public int quality;
    public bool isAvailable;
    public qualityWithStatus(int ex_quality)
    {
        quality = ex_quality;
        isAvailable = true;
    }
}
...
if (gQualDict.Count > 0 && gQualDict.Values.Aggregate((a, b) => b + a) >= 40)
{
    string resultMessage = string.Empty;
    List<string> combinationsFound = new List<string>();
    Random rnd = new Random();
    for (int iterator = 0; iterator < 100000; iterator++)
    {
        List<qualityWithStatus> tempQualList = new List<qualityWithStatus>();
        foreach (int qualValue in gQualDict.Values)
            tempQualList.Add(new qualityWithStatus(qualValue));
        int currentSumm = 0;
        //prepare list of numbers like 0,1,2,3,4,5,6,7,8,9,...
        List<int> numberList = Enumerable.Range(0, tempQualList.Count).ToList();
        do
        {
            //get random number from 0 to count of prepared list numbers
            int randomValue = numberList[rnd.Next(0, numberList.Count)];
            //remove this number from prepared list so it will not appear again
            numberList.Remove(randomValue);
            if (tempQualList[randomValue].isAvailable)
            {
                currentSumm += tempQualList[randomValue].quality;
                tempQualList[randomValue].isAvailable = false;
            }
        }
        while (currentSumm < 40);
        if (currentSumm == 40)
        {
            gQualDict.Clear();
            enableQualityCombinationModeToolStripMenuItem_Click(enableQualityCombinationModeToolStripMenuItem, null);
            resultMessage += formQualityAnswer(tempQualList) + Environment.NewLine;
            break;
        }
        else if (currentSumm < 43)
        {
            string answer = formQualityAnswer(tempQualList);
            if (!combinationsFound.Contains(answer))
            {
                combinationsFound.Add(answer);
                resultMessage += answer + " (" + currentSumm + ")" + Environment.NewLine;
                if (combinationsFound.Count > 7)
                    break;
            }
        }
    }

private string formQualityAnswer(List<qualityWithStatus> ex_qualList)
{
    List<int> answer = new List<int>();
    foreach (qualityWithStatus qws in ex_qualList)
        if (!qws.isAvailable)
            answer.Add(qws.quality);
    answer.Sort();
    return string.Join(" + ", answer);
}