90. Subsets II

Here is C# practice using recursive solution, I studied the code written by an Amazon engineer. 

It is important for me to learn how to write a simple recursive solution. Since my iterative solution takes me more than one hour to complete the code and testing.

I like to learn how to write a simple recursive solution, so I can solve it in less than 15 minutes. One thing I can do is to study code, and then write down how I understand the code.

public class Solution {
    /// <summary>
        /// June 22, 2019
        /// study code
        /// https://leetcode.com/problems/subsets-ii/discuss/30214/C-recursive
        /// The importance to learn to write a recursive function.
        /// I need to finish the code in less than 15 minutes. 
        /// I need to shorten the time to write a solution, recursive function is the first choice. 
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        public  IList<IList<int>> SubsetsWithDup(int[] numbers)
        {
            // sets - good name? 
            var sets = new List<IList<int>>();

            Array.Sort(numbers);

            buildSubsets(numbers, sets, 0, new List<int>());

            return sets;
        }

        /// <summary>
        /// I need to learn how to write a recursive solution. 
        /// </summary>
        /// <param name="numbers"></param>
        /// <param name="sets"></param>
        /// <param name="index"></param>
        /// <param name="currentSet"></param>
        private void buildSubsets(int[] numbers, IList<IList<int>> sets, int index, List<int> currentSet)
        {
            sets.Add(currentSet);

            for (int i = index; i < numbers.Length; i++)
            {
                var current = numbers[i];

                var nextSet = new List<int>(currentSet); // copy the list

                nextSet.Add(current);

                buildSubsets(numbers, sets, i + 1, nextSet);

                // input list is sorted
                while (i < numbers.Length - 1 && numbers[i] == numbers[i + 1])
                {
                    i++;
                }
            }
        }
}