Переполнение стека ни в коем случае не единственная проблема вашего кода, но давайте начнем с этого. GetCombinations вызывает себя рекурсивно. Когда вы получаете сотни тысяч коллов, у вас заканчивается стек. Вы не можете использовать системный стек в этом случае, вам нужно больше места для хранения данных.
Здесь вы ищете только одно решение, но код, очевидно, написан с намерением вернуть все отдельные наборы. Но вам стоит пересмотреть подход. Вы создаете все варианты, а затем выбираете уникальные наборы и отбрасываете остальные. Это очень дорого. Мол, на несколько порядков хуже. Вы должны напрямую создавать отдельные наборы. Например, если у вас есть номер 6, следующим номером может быть 6, 5 или 4, но не 7.
Следующая большая проблема - это ситуации без решения. Вы можете довольно быстро найти какое-то решение, если оно существует. Но если нет, вы получите l oop во многих комбинациях. Вы можете использовать программирование Dynami c, чтобы решить эту проблему. Он сообщит вам, какие суммы действительны для контейнеров, которые у вас нет. И вы можете использовать его для дальнейшего повышения эффективности рекурсии.
Вы создаете новый List каждый раз, когда возвращаетесь из функции. Это безопасный подход. Но часто можно просто вернуть тот же список и изменить его. Для случаев вроде GetCombinations(...).Count() это более эффективно. Давайте соберем все вместе.
static IEnumerable<List<int>> GetCombinations(int[] set, int sum)
{
var orderedSet = set.Distinct().OrderByDescending(o => o).ToArray();
bool[] valid = new bool[sum + 1];
valid[0] = true;
for (int i = 0; i < sum; ++i)
{
if (valid[i])
{
for (int j = 0; j < orderedSet.Length; ++j)
{
int next = i + orderedSet[j];
if (next < valid.Length)
{
valid[next] = true;
}
}
}
}
if (!valid[sum])
{
return new List<int>[0]; //no solution
}
return GetCombinationsRecurse(orderedSet, sum, new List<int>(), valid, 0);
//return GetCombinationsNoRecurse(orderedSet, sum, valid);
}
static IEnumerable<List<int>> GetCombinationsRecurse(int[] set, int sum,
List<int> values, bool[] valid, int setIterator)
{
for (var i = setIterator; i < set.Length; i++)
{
var left = sum - set[i];
if (left < 0 || !valid[left])
{
continue;
}
values.Add(set[i]);
if (left == 0)
{
yield return values;
}
else
{
foreach (var s in GetCombinationsRecurse(set, left, values, valid, i))
{
yield return s;
}
}
values.RemoveAt(values.Count - 1);
}
}
Я привел здесь рекурсивную версию, потому что она соответствует вашему исходному коду и ей легче следовать. Но переполнение стека для больших чисел явно остается. Рекурсивную функцию всегда можно переписать в нерекурсивную версию. Вам нужно использовать некую структуру данных вместо системного стека. Либо стек, либо массив, либо что-то еще. Но, как правило, это не красиво
static IEnumerable<List<int>> GetCombinationsNoRecurse(int[] set, int sum, bool[] valid)
{
List<int> sums = new List<int>() { 0 };
List<int> setIterators = new List<int>() { 0 };
int iter = 0;
List<int> values = new List<int>() { set[iter] };
while (true)
{
int actSum = sums[iter] + values[iter];
int left = sum - actSum;
if (left == 0)
{
yield return values;
}
if (left <= 0 || !valid[left])
{
while (++setIterators[iter] >= set.Length)
{
if (--iter < 0) { yield break; }
values.RemoveAt(values.Count - 1);
}
values[iter] = set[setIterators[iter]];
continue;
}
{ // left > 0
if (sums.Count > iter + 1)
{
sums[iter + 1] = actSum;
setIterators[iter + 1] = setIterators[iter];
}
else
{
sums.Add(actSum);
setIterators.Add(setIterators[iter]);
}
values.Add(values[iter]);
iter++;
}
}
}