0077-Combinations.cs

using System;
using Xunit;
using Util;
using System.Linq;
using System.Collections.Generic;
using System.Text;

namespace Combinations
{
    public class Solution
    {
        public IList<IList<int>> Combine(int n, int k)
        {
            IList<IList<int>> combList = new List<IList<int>>();
            for (var i = 0; i < k; i++)
            {
                combList = comb(n, k, combList);
            }
            return combList;
        }
        IList<IList<int>> comb(int n, int k, IList<IList<int>> combList)
        {
            IList<IList<int>> combList2 = new List<IList<int>>();
            if (combList.Count == 0)
            {
                for (var i = 1; i <= (n - k + 1); i++)
                {
                    combList2.Add(new List<int> { i });
                }
            }
            else
            {
                foreach (var i in combList)
                {
                    var last = i.Last();
                    for (var j = last + 1; j <= n; j++)
                    {
                        var x = new List<int>(i);
                        x.Add(j);
                        combList2.Add(x);
                    }
                }
            }
            return combList2;
        }
    }
    public class Test
    {
        static void Verify(int n, int k, IList<IList<int>> exp)
        {
            Console.WriteLine($"{n}, {k}");
            IList<IList<int>> res;
            using (new Timeit())
            {
                res = new Solution().Combine(n, k);
            }
            var x = res.Select(i => i.ToArray()).ToArray();
            // Console.WriteLine(x.Int2dToJson());
            Assert.Equal(exp, x);
        }
        static public void Run()
        {
            Console.WriteLine(typeof(Solution).Namespace);

            var input = @"
4
2
[ [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] ]
";
            var lines = input.CleanInput();
            int n, k;
            IList<IList<int>> exp;
            int idx = 0;
            while (idx < lines.Length)
            {
                n = int.Parse(lines[idx++]);
                k = int.Parse(lines[idx++]);
                exp = lines[idx++].JsonToInt2d();
                Verify(n, k, exp);
            }
        }
    }
}