从状态空间树构建回溯函数时，如何决定递归调用传i+1还是j+1？

从状态空间树构建回溯函数时，如何决定递归调用传i+1还是j+1？ #

从状态空间树图中得出的核心见解：

• 包含/排除模式（O(2^n)）
  • 适用于每个元素只有包含或排除两种选择的场景
  • 实现时无需使用循环

  递归调用通常通过推进索引（i+1）来移动到下一个元素

void backtrack(int i, vector<int>& subset) {
    if (i == n) {
        // 处理子集
        return;
    }

    // 包含第i个元素
    subset.push_back(arr[i]);
    backtrack(i + 1, subset);
    subset.pop_back(); // 撤销选择

    // 排除第i个元素
    backtrack(i + 1, subset);
}

示例：子集问题

• 基于循环的模式（O(n!)）
  • 适用于每个递归层级有多个选择的场景
  • 实现时需要用for循环遍历所有可选元素

  若元素可重复使用，则传入不变的j；若每个元素仅能使用一次，则传入j+1以避免重复选取同一元素

void backtrack(int i, vector<int>& combination) {
    if (combination.size() == target_size) {
        // 处理有效组合
        return;
    }

    for (int j= i; j < n; j++) {
        if (isValid(arr[j])) {  // 剪枝条件
            combination.push_back(arr[j]);
            backtrack(j + 1, combination);  // 传递j+1确保元素不重复使用
            combination.pop_back();  // 撤销选择
        }
    }
}

示例：组合问题

• 撤销操作的注意事项
  • 仅当部分解决方案按引用传递时，才需要执行撤销操作（即回溯步骤）

内容的提问来源于stack exchange，提问作者Mr. Ghosh