Backtracking C++ solution


  • 18
    Y
    class Solution {
        void utils(bitset<32>& bits, vector<int>& result, int k){
            if (k==0) {
                result.push_back(bits.to_ulong());
            }
            else {
                utils(bits, result, k-1);
                bits.flip(k-1);
                utils(bits, result, k-1);
            }
        }
    public:
        vector<int> grayCode(int n) {
            bitset<32> bits;
            vector<int> result;
            utils(bits, result, n);
            return result;
        }
    };

  • 0
    T

    Hi, it is a brilliant idea! Just wanna know why it is backtracking?


  • 3
    Z

    Great idea!!! Based on your idea I implement in JAVA

        int nums = 0;
        public List<Integer> grayCode(int n) {
            List<Integer> ret = new ArrayList<>();
            backTrack(n, ret);
            return ret;
        }
        
        private void backTrack(int n, List<Integer> ret) {
            if (n == 0) {
                ret.add(nums);
                return;
            }
            else {
                backTrack(n - 1, ret);
                nums ^= (1 << n - 1);
                backTrack(n - 1, ret);
            }
        }
    

  • 0
    N

    Very elegant solution. But I'm confused about this idea. Could anyone explain it? Thanks in advance.


Log in to reply
 

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