Simple backtracking solution


  • 0
    L

    This is a simple backtracking problem in the form:

    f(n) = 0|1 + f(n-1)

    as the problem statement says, there could be multiple answers. Well, in order to pass the test, we watch the example and found it is kind of:

    f(n) = (0 + f(n-1)) union ( 1 + f(n-1) in reverse order )

    then we have this straightforward solution:

    class Solution {
        
    public:
        vector<int> grayCode(int n) {
            vector<int> result;
            if (n==0) {
                result.push_back(0);
                return result;
            }
    
            vector<int> subValues = grayCode(n-1);
            
            for(auto v : subValues) {
                result.push_back(v);
            }
            
            for (int i=subValues.size()-1;i>=0;i--) {
                result.push_back((1<<(n-1)) + subValues[i]);
            }
            
            return result;
        }
    };

Log in to reply
 

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