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]]

    }

}