Recursion over substitution combinations

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

namespace Whatever
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] matrix = new int[4, 4] { { 1, 0, 0, 0 }, { 0, 2, 0, 0 }, { 0, 0, 3, 0 }, { 0, 0, 0, 0 } };
            DoThing(matrix, 4, 4);
        }

        static int[][] startGenerate(int[] nums, int length, out int rows)
        {
            rows=1;
            for (int i = 0; i < length; i++)
                rows *= nums[i];

            int[][] answers = new int[rows][];

            for (int i = 0; i < rows; i++)
                answers[i] = new int[length];

            int index = 0;

            generate(nums, length, 0, new int[length], answers,ref index);

            return answers;
        }

        static void generate(int[] a, int len, int x, int[] cur, int[][] ans,ref int index)
        {
            if (x >= len)
            {
                cur.CopyTo(ans[index++], 0);
                return;
            }

            for (int i = 0; i < a[x]; i++)
            {
                cur[x] = i;
                generate(a, len, x + 1, cur, ans,ref index);
            }

            cur[x] = 0;
        }

        static void DoThing(int[,] m, int rows, int cols)
        {
            int numOfSubs=0;
            int[][] subs = new int[rows * cols][];

            //Get all the substitution locations, the numbers to substitute and how many there are
            for (int i=0;i<rows;i++)
                for (int j = 0; j < cols; j++)
                {
                    if (m[i, j] > 0)
                    {
                        int[] sub;
                        int numSubsForThisEntry = GetSubs(m[i,j], out sub);
                        int[] subRecord = new int[numSubsForThisEntry + 3];
                        subRecord[0] = numSubsForThisEntry;
                        subRecord[1] = i;
                        subRecord[2] = j;
                        sub.CopyTo(subRecord, 3);
                        subs[numOfSubs++] = subRecord;
                    }
                }

            if (numOfSubs == 0) return; //Don't recurse if no substitutions

            PrintArray(m, rows, cols, "Number of Subs for this array: " + numOfSubs);

            //generate an array of all possible substutions
            int[] generateNums = new int[numOfSubs];
            for (int i = 0; i < numOfSubs; i++)
                generateNums[i] = subs[i][0];
            int totalCombinations;
            int[][] arrayOfSubstitutionIndexes = startGenerate(generateNums, numOfSubs, out totalCombinations);

            //go over each set of substitutions
            for (int i = 0; i < totalCombinations; i++)
            {
                //with this set of substitution indexes
                //make a substitution at every substitution location identified previously
                int[] subIndexes = arrayOfSubstitutionIndexes[i];
                for (int j = 0; j < numOfSubs; j++)
                {
                    m[subs[j][1], subs[j][2]] = subs[j][3 + subIndexes[j]];
                }


                //Transform
                //DoTransform(m, rows, cols);

                //Recursive call

                DoThing(m, rows, cols);

            }


        }

        static int GetSubs(int num, out int[] subs)
        {
            if (num == 1)
                subs = new int[] { 2, 3 };
            else if (num == 2)
                subs = new int[] { 3, 4 };
            else if (num == 3)
                subs = new int[] { 5 , 5 };
            else
                subs = new int[] {0 , 0};

            return 2;
        }

        static void PrintArray(int[,] m, int rows, int cols, string header)
        {
            Console.WriteLine(header);
            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < cols; j++)
                {
                    Console.Write(m[i, j] + "\t");
                }
                Console.WriteLine("");
            }
        }
    }
}