Задача. Комбинированная сумма
Задача. Дан массив чисел-кандидатов и целевое число. Необходимо найти все уникальные комбинации в кандидатах, в которых сумма чисел-кандидатов равна целевому числу.
При этом каждое число в кандидатах может быть использовано в комбинации только один раз.
Примечание: Набор решений не должен содержать дублирующихся комбинаций.
Input:
- [2,5,2,1,2], target = 5
Output:
- [[1,2,2], [5]]
Разбор
Это одна из классических задач, которые решаются методом поиска с возвратом (backtracking).
Исходный массив предварительно нужно отсортировать, это необходимо, чтобы мы могли легко убирать дублирующие элементы из комбинациий.
Суть алгоритма в использовании рекурсивной функции, где параметрами будут исходный массив, текущая комбинация элементов, текущий индекс, с которого мы делаем новый перебор.
Также мы будем передавать текущую сумму элементов из комбинации, чтобы нам не приходилось суммировать саму комбинацию в каждой итерации.
В рекурсивной функции точками выхода будут 2 условия:
- Сумма больше целевого числа.
- Сумма равна целевому числу: записываем в результируюший список текущую комбинацию элементов.
Далее будем перебирать элементы от индекса из параметров функции до конца исходного массива. Чтобы решение не содержало дублирующих комбинаций, пропустим повторяющие элементы.
И наконец сам алгоритм поиска с возвратом:
- мы делаем предположение для текущего элемента и добавляем его в текущую комбинацию и рекурсивно вызываем эту же функцию.
- После мы убираем последний элемент из текущей комбинации, тем самым мы проверили наше предположение для текущего элемента.
Смотрите детали реализации ниже.
Реализация
public static IList<IList<int>> CombinationSum(int[] candidates, int target) {
Array.Sort(candidates);
Target = target;
Output = new List<IList<int>>();
Backtracking(candidates, new List<int>(), 0, 0);
return Output;
}
public static void Backtracking(int[] input, List<int> curr, int index, int sum)
{
if (sum > Target)
{
return;
}
if (sum == Target) {
Output.Add(new List<int>(curr));
return;
}
for (int i = index; i < input.Length; i++)
{
if (i > index && input[i] == input[i - 1])
continue; // пропускаем дубликаты
curr.Add(input[i]);
Backtracking(input, curr, i + 1, sum + input[i]);
curr.RemoveAt(curr.Count - 1);
}
}https://gist.github.com/unilecs/dac3557ea2bcff8760f68b233070f284