using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Counting Subsets of Size K");    

        int result = NChooseK(5, 3);

        Console.WriteLine(result);

        int resultDp = NChooseKDP(5, 3);

        Console.WriteLine(resultDp);

    }

    public static int NChooseK(int n, int k)

    {

        if(k ==0 || k == n)

            return 1;

        return NChooseK(n-1, k) + NChooseK(n-1, k-1);

    }

    public static int NChooseKDP(int n, int k)

    {

        int[,] c = new int[n+1, k+1];

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

        {

            for(int j=0; j <= Math.Min(i, k); j++)

            {

                //Base Case

                if(j == i || j == 0)

                    c[i, j] = 1;

                else

                    c[i, j] = c[i-1, j] + c[i-1, j-1];

            }

        }

        return c[n, k];

    }

}