回溯法是一种常用的算法，它能够在解决组合优化问题时发挥重要作用。在C++中，回溯法可以被用来实现任意集合中选取r个数的排列。

首先，我们需要定义一个vector来存储我们的结果。这个vector的大小应该为r，因为我们要输出r个数的排列。我们还需要一个数组visited来记录每个数字是否已经被访问过。接下来，我们可以通过递归函数来实现回溯法。

在递归函数中，我们需要从1~n中选择一个数字。当我们选择一个数字后，我们需要将它标记为visited，将它加入结果vector中，然后递归地调用函数来选择下一个数字。如果我们已经选择了r个数字，那么我们就可以输出这个排列并返回。如果我们不能再选择数字，那么我们需要回溯到前一个状态，并尝试选择不同的数字。

整个过程可以用如下代码实现：

#include

#include

using namespace std;

void backtracking(vector & res, int visited[], int n, int r) {

  if (res.size() == r) { //已经选取了r个数字，输出结果

    for (auto num : res)

      cout << num << " ";

    cout << endl;

    return;

  }

  for (int i = 1; i <= n; i++) { //枚举1~n中的数字

    if (!visited[i]) { //如果数字没有被选取过

      visited[i] = 1; //标记该数字被选取

      res.push_back(i); //将数字加入结果vector中

      backtracking(res, visited, n, r); //递归地选择下一个数字

      visited[i] = 0; //回溯到上一个状态，重置visited

      res.pop_back(); //从结果vector中删除该数字

    }

  }

}

int main() {

  int n, r;

  cin >> n >> r;

  vector res;

  int visited[n+1] = {0}; //数组初始化为0

  backtracking(res, visited, n, r);

  return 0;

}

在上面的代码中，我们首先从标准输入中读取了n和r。接着，我们定义一个空的vector和一个大小为n+1的visited数组。visited数组来标记每个数字是否被访问过。初始化时，visited数组的所有元素都为0，表示所有数字都没有被访问过。

最后，我们调用backtracking函数来进行回溯。在该函数中，我们先检查结果vector的大小是否等于r。如果是，我们就输出这个排列。否则，我们从1~n中枚举数字，并尝试将其加入结果vector中。如果当前数字没有被访问过，我们就将它标记为visited，并进行递归调用。如果我们不能再选择数字，那么我们就回溯到上一个状态，并尝试选择不同的数字。

最终，我们可以得到所有可能的排列。这是一种非常实用的算法，可以被用来解决很多组合选择问题。

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政