using System;

using System.Collections.Generic;

​

public class Solution

{

    public IList<IList<long>> CombinationSum(long[] candidates, long target)

    {

        IList<long> path = new List<long>();

        IList<IList<long>> result = new List<IList<long>>();

        CombinationSumHelper(candidates, target, 0, path, result);

        return result;

    }

​

    private void CombinationSumHelper(long[] candidates, long target, int index, IList<long> path, IList<IList<long>> result)

    {

        // if taget is zero it means this path is equal to taget so add it to result and return

        if (target == 0)

        {

            result.Add(new List<long>(path));

            return;

        }

​

​

        for (int i = index; i < candidates.Length; i++)

        {

            // if condition is true continue with current element and current path otherwise try differnt elemet from candidates array

            if (target - candidates[i] >= 0)

            {

                path.Add(candidates[i]);

                CombinationSumHelper(candidates, target - candidates[i], i+1, path, result);

                // remove last for back tracking.

                path.RemoveAt(path.Count - 1);

            }

        }

    }

}

​

public class Program

{

    public static void Main()

        {

            var candidates = new long[] {

2179766000,

1743060443,

132947725,

264105310,

119484343,

205421254,

109289309,

2238213549,

39408045,

21329892,

408936754, 

185078771,

48116341,

225791674,

84093797,

62100000,

88200000,

170518238,

1091691464,

474964000,

391227183,

39006868,

139367514,

12146777,

43419471,

21656048,

468199560,

8731396,

4498603,

85674160,

27753478,

38491791,

78810559,

22312203,

13500000,

35841000,

25097659,

342240624,

140112000,

108479729,

38066776,

62170500,

21032111,

2987041,

165691825, 

3351230,

1580058,

30021140,

13360077,

25000000,

3696000,

3600000,

​

            };

            var target = 16629575554;

​

            var solution = new Solution();

            var result = solution.CombinationSum(candidates, target);

            foreach (var combination in result)

            {

                Console.WriteLine(string.Join(",", combination));

            }

        }

}