// C# program for the above approach

using System;

using System.Collections.Generic;

​

​

public class GFG {

​

    static List<List<int> >

    combinationSum(List<int> arr, int sum)

    {

        List<List<int> > ans

            = new List<List<int> >();

        List<int> temp = new List<int>();

​

        // first do hashing since hashset does not always

        // sort

        // removing the duplicates using HashSet and

        // Sorting the List

​

        HashSet<int> set = new HashSet<int>(arr);

        arr.Clear();

        arr.AddRange(set);

        arr.Sort();

​

        findNumbers(ans, arr, sum, 0, temp);

        return ans;

    }

​

    static void

    findNumbers(List<List<int> > ans,

                List<int> arr, int sum, int index,

                List<int> temp)

    {

​

        if (sum == 0) {

​

            // Adding deep copy of list to ans

​

            ans.Add(new List<int>(temp));

            return;

        }

​

        for (int i = index; i < arr.Count; i++) {

​

            // checking that sum does not become negative

​

            if ((sum - arr[i]) >= 0) {

​

                // Adding element which can contribute to

                // sum

​

                temp.Add(arr[i]);

​

                findNumbers(ans, arr, sum - arr[i], i,

                            temp);

​

                // removing element from list (backtracking)

                temp.Remove(arr[i]);

            }

        }

    }

​

    // Driver Code

​

    public static void Main()

    {

        List<int> arr = new List<int>();

        arr.Add(2);

        arr.Add(4);

        arr.Add(6);

        arr.Add(8);

​

        int sum = 8;

​

        List<List<int> > ans

            = combinationSum(arr, sum);

​

        // If result is empty, then

        if (ans.Count == 0) {

            Console.WriteLine("Empty");

            return;

        }

​

        // print all combinations stored in ans

​

        for (int i = 0; i < ans.Count; i++) {

String str ="";

            for (int j = 0; j < ans[i].Count; j++) {

                //Console.Write(ans[i][j] + " ");

                str+=ans[i][j];

            }

            int n = str.Length;

            permute(str, 0, n-1);

            Console.Write(") ");

        }

    }

    private static void permute(String str,

                                int l, int r)

    {

        if (l == r)

            Console.WriteLine(str);

        else

        {

            for (int i = l; i <= r; i++)

            {

                str = swap(str, l, i);

                permute(str, l + 1, r);

                str = swap(str, l, i);

            }

        }

    }

    public static String swap(String a,

                            int i, int j)

    {

        char temp;

        char[] charArray = a.ToCharArray();

        temp = charArray[i] ;

        charArray[i] = charArray[j];

        charArray[j] = temp;

        string s = new string(charArray);

        return s;

    }

}

​

// This code is contributed by ShubhamSingh10

​