Simple C# recursive solution


  • 0
    S

    For these kind of problem, it is important to think about the exit condition when recursion will exit. In this problem, we want to firstly find out how many binaries representations there could be given number n.

    if n == 0, we will only have 1 representation, which is "0"
    if n == 1, we can only have 1 bit in the binary, which could be either "0" or "1". In this case, "{0}", and "{1}".

    We can see for one bit, there could have two solutions, which either 0 or 1. Then we can write a recursive solution to keep track of how many "n" left, -- the bits.

    (Note: The judge will only check certain sequence, but according to the def of this question, any sequence should be accepted)

    public class Solution {
    public IList<int> GrayCode(int n) {
    if (n == 0)
    {
    return new List<int>() {0};
    }
    IList<int> result = new List<int>();
    GenerateGrayCode(result, n, String.Empty);

        return result;
    }
    
    public void GenerateGrayCode(IList<int> result, int n, string tempNum)
    {
        if (n == 0)
        {
            Console.WriteLine(tempNum);
            result.Add(Convert.ToInt32(Convert.ToInt32(tempNum, 2).ToString(), 10));
            return;
        }
        
        GenerateGrayCode(result, n-1, tempNum+"0");
        GenerateGrayCode(result, n-1, tempNum+"1");
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.