C# standard depth first search with back tracking
March 21, 2019\nIt is the hard level algorithm. I like to share the standard depth first search using back tracking technique to solve the problem. What I did i
March 21, 2019\nIt is the hard level algorithm. I like to share the standard depth first search using back tracking technique to solve the problem. What I did is to study weekly contest 128 ranking 13 player\'s code, and then I wrote one based on my understanding. \n\nHere are steps to follow:\n1. Brute force solution, from rightmost digit, enumerate all the possible digit; \n2. Go to next digit by moving to left side, skip those used digits. Use one array with size 10 to record used digit from 0 to 9. \n3. Combine step 1 and step2, the brute force solution time complexity O(10!)\n4. Do not forget to back tracking\n```\nusing System;\nusing System.Collections.Generic;\nusing System.Diagnostics;\nusing System.Linq;\nusing System.Text;\nusing System.Threading.Tasks;\n\nnamespace _1015_number_with_repeated_digits_13\n{\n    class Program\n    {\n        static void Main(string[] args)\n        {\n            NumDupDigitsAtMostN(872427638);\n            Debug.Assert(value == 10); \n        }\n\n        public static int    value = 0; \n        public static bool[] taken = new bool[10];\n\n        /// <summary>\n        /// March 20, 2019\n        /// study code based on ranking No. 13, VladaMG98\n        /// https://leetcode.com/contest/weekly-contest-128/ranking/\n        /// </summary>\n        /// <param name="N"></param>\n        /// <returns></returns>\n        public static int NumDupDigitsAtMostN(int N)\n        {            \n            return N - getAllDifferent(N) + 1; \n        }\n\n        private static int getAllDifferent(int N)\n        {\n            value = 0;\n            for (int i = 0; i < taken.Length; i++)\n            {\n                taken[i] = false; \n            }\n\n            recursive(0, 0, N);\n            return value; \n        }\n\n        /// <summary>\n        /// Brute force solution\n        /// Make sure that all numbers in the integer are distinct, less than and equal N.\n        /// Problem statement:\n        /// Given a positive integer N, return the number of positive integers less than or \n        /// equal to N that have at least 1 repeated digit.\n        /// Start from rightmost digit. \n        /// </summary>\n        /// <param name="number"></param>\n        /// <param name="digit"></param>\n        /// <param name="N"></param>\n        private static void recursive(double number, int digit, int N)\n        {\n            if (number > N)\n            {\n                return; \n            }\n\n            // current number with value number is the one. \n            value += 1;\n\n            // Fix timeout bug\n            if (number * 10 > N)\n            {\n                return;\n            }\n\n            for (int x = 0; x < 10; x++)\n            {\n                if (taken[x])\n                {\n                    continue; \n                }\n\n                // make sure that the number is positive number\n                var numberIsZero = digit == 0 && x == 0;\n                if (numberIsZero)\n                {\n                    continue;\n                }\n\n                taken[x] = true;\n                recursive(number * 10 + x, digit + 1, N);\n                \n                // backtracking\n                taken[x] = false; \n            }\n        }\n    }\n}\n```
[]