Skip to content

Instantly share code, notes, and snippets.

@unilecs
Created February 29, 2024 05:54
Show Gist options
  • Save unilecs/dac3557ea2bcff8760f68b233070f284 to your computer and use it in GitHub Desktop.
Save unilecs/dac3557ea2bcff8760f68b233070f284 to your computer and use it in GitHub Desktop.
Задача: Комбинированная сумма
using System;
using System.Linq;
using System.Collections.Generic;
public class Program
{
private static int Target;
public static IList<IList<int>> Output;
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);
}
}
private static void ShowListOfList(IList<IList<int>> list)
{
Console.WriteLine($"[{string.Join(", ", list.Select(x => "[" + string.Join(", ", x) + "]"))}]");
}
public static void Main()
{
Console.WriteLine("UniLecs");
// tests
ShowListOfList(CombinationSum(new int[] { 2,5,2,1,2 }, 5)); // [[1, 2, 2], [5]]
ShowListOfList(CombinationSum(new int[] { 10,1,2,7,6,1,5 }, 8)); // [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment