Simple backtracking solution

  • 0

    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 {
        vector<int> grayCode(int n) {
            vector<int> result;
            if (n==0) {
                return result;
            vector<int> subValues = grayCode(n-1);
            for(auto v : subValues) {
            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.