如何用回溯法打印n位二进制格雷码？现有递归代码改造咨询

你的代码是不是回溯法？ #

不是。你的代码是基于格雷码的递归构造特性实现的分治法：

• 核心思路是用n-1位格雷码生成n位：先给n-1位的所有元素前加"0"，再逆序遍历n-1位元素并前加"1"，合并得到结果。
• 回溯法的核心是尝试-回退：逐步构建解，当当前路径不符合要求时回退，换其他选择继续试。但你的代码没有任何回退逻辑，只是递归拼接结果，完全是分治法的路子。

改成回溯法的实现方式 #

回溯法生成格雷码的思路是：从全0的n位字符串开始，每次尝试翻转当前字符串的某一位得到新字符串，只要这个新字符串没被用过，就加入结果集，接着从这个新字符串继续递归，直到生成所有2^n个格雷码。

修改后的代码如下：

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

void backtrack(int n, string current, unordered_set<string>& visited, vector<string>& result) {
    // 凑够所有格雷码就停止
    if (result.size() == (1 << n)) {
        return;
    }
    // 标记当前格雷码已用过，加入结果
    visited.insert(current);
    result.push_back(current);
    
    // 尝试翻转每一位，生成新的格雷码
    for (int i = 0; i < n; ++i) {
        string next_code = current;
        // 把第i位翻转：0变1，1变0
        next_code[i] = (next_code[i] == '0') ? '1' : '0';
        // 如果这个新格雷码没出现过，就继续递归
        if (visited.find(next_code) == visited.end()) {
            backtrack(n, next_code, visited, result);
            // 这里不需要手动回退，递归返回后会自动尝试下一位的翻转
        }
    }
}

vector<string> grayCode(int n) {
    vector<string> result;
    if (n <= 0) {
        return {"0"};
    }
    // 从全0的n位字符串开始
    string start(n, '0');
    unordered_set<string> visited;
    backtrack(n, start, visited, result);
    return result;
}

int main() {
    vector<string> gcode = grayCode(4);
    for (const string& code : gcode) {
        cout << code << "    ";
    }
    return 0;
}

代码说明 #

• 用unordered_set记录已经生成的格雷码，避免重复添加。
• 每次递归时，翻转当前字符串的每一位生成新候选，只要候选没被用过，就继续往下走，直到收集齐所有2^n个格雷码。
• 这种方式完全符合回溯法“尝试-推进-（隐含回退）”的核心逻辑：当某条路径走到头（凑够所有码），递归返回后会自动尝试其他可能的翻转方向。

内容的提问来源于stack exchange，提问作者Hanzo