本文共 863 字，大约阅读时间需要 2 分钟。

描述

给定两个整数 n 和 k，目标是生成 1 到 n 之间所有可能的 k 元组的组合。这个问题可以通过回溯算法高效地解决，暴力枚举虽然可行，但效率较低。我们可以通过递归的方式逐一尝试每个数，直到找到满足条件的组合。

思路

这个问题和组合生成问题类似。我们可以使用回溯算法来实现，即每次尝试选择下一个数，直到选择了k个数为止。这种方法的time complexity是 O(nPk)，也就是 O(n!/(n-k)!))，其中n!是n的阶乘。

解答

想了解如何用C++实现这一功能吗？来看以下代码：

vector
   
    
     > combine(int n, int k) {    vector
     
      
       > res;    vector
       
         v_tmp;    int current;        void backTrack(int start) {        if(v_tmp.size() == k) {            res.push_back(v_tmp);            return;        }        for(int i = start; i <= n; ++i) {            v_tmp.push_back(i);            backTrack(i + 1);            v_tmp.pop_back();        }    }        backTrack(1);    return res;}
       
      
     
    
   

如何使用

将该函数调用如下：

vector
   
    
     > result = combine(n, k);
    
   

结论

通过上述代码，我们可以轻松地生成所有k个数的组合。回溯算法通过深度优先搜索逐一尝试每个可能的路径，从而生成所有满足条件的组合。这是解决此类问题最直接有效的方法之一。

转载地址：http://xiusz.baihongyu.com/