Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Approach: DFS

        public static IList<IList<int>> Combine(int n, int k) 

        {

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

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

            FindCombinatons(n, k, 1, ref result, currCombination);

            return result;

        }

        private static void FindCombinatons(int n, int k, int start, ref List<IList<int>> result, List<int> currCombination)

        {

            if (k == 0)

            {

                result.Add(new List<int>(currCombination));

            }

            for (int i = start; i <= n; ++i)

            {

                currCombination.Add(i);

                FindCombinatons(n, k - 1, i + 1, ref result, currCombination);

                currCombination.RemoveAt(currCombination.Count - 1);

            }

        }