C++怎么实现一个回溯算法_C++解决组合、排列、子集等搜索问题的通用框架

void backtrack(vector& path, 其他参数) {
    if (满足结束条件) {
        记录结果;
        return;
    }
    
    for (选择 in 选择列表) {
        做选择：将选择加入 path;
        backtrack(path, 其他参数);
        撤销选择：从 path 移除该选择;
    }
}

vector> combine(int n, int k) {
    vector> res;
    vector path;
    
    function backtrack = [&](int start) {
        if (path.size() == k) {
            res.push_back(path);
            return;
        }
        
        for (int i = start; i <= n; ++i) {
            path.push_back(i);
            backtrack(i + 1);  // 下一轮从 i+1 开始，保证升序
            path.pop_back();
        }
    };
    
    backtrack(1);
    return res;
}

vector> permute(vector& nums) {
    vector> res;
    vector path;
    vector used(nums.size(), false);
    
    function backtrack = [&]() {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }
        
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue;
            
            path.push_back(nums[i]);
            used[i] = true;
            backtrack();
            path.pop_back();
            used[i] = false;  // 回溯恢复状态
        }
    };
    
    backtrack();
    return res;
}

vector> subsets(vector& nums) {
    vector> res;
    vector path;
    
    function backtrack = [&](int start) {
        res.push_back(path);  // 每次进入都记录，包括空集
        
        for (int i = start; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            backtrack(i + 1);
            path.pop_back();
        }
    };
    
    backtrack(0);
    return res;
}