C ++中的组合和IIII

考虑到我们必须生成k个数字的所有可能组合，这些数字加起来等于n，因为只能使用1到9之间的数字。每个组合应该是一组唯一的数字。所有数字均应为正，并且解决方案不得包含重复的组合。因此，如果k = 3且n = 9，则可能的组合为[[1,2,6]，[1,3,5]，[2,3,4]

为了解决这个问题，我们将遵循以下步骤-

• 假设我们将通过形成称为“求解”的方法来解决此问题。这将是递归方法，将采用k，n，临时数组并开始。开始时是1

• 如果n = 0

• 将我插入临时

• 解（k，n – i，温度，i + 1）

• 删除temp中的最后一个元素

• 如果temp的大小= k，则将temp插入res并返回

• 对于i：=开始最小为9和n

• 主要方法会像

• 创建一个称为temp的空白向量

• 解(k,n,temp)

• 返回资源

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector < vector <int> > res;
   void solve(int k, int n, vector <int> temp, int start = 1){
      if(n == 0){
         if(temp.size() == k){
            res.push_back(temp);
         }
         return;
      }
      for(int i = start ; i <= min(9, n); i++){
         temp.push_back(i);
         solve(k, n - i, temp, i + 1);
         temp.pop_back();
      }
   }
   vector<vector<int>> combinationSum3(int k, int n) {
      res.clear();
      vector <int> temp;
      solve(k, n, temp);
      return res;
   }
};
main(){
   Solution ob;
   print_vector(ob.combinationSum3(2, 9));
}

输入值

3
9

输出结果

[[1, 8, ],[2, 7, ],[3, 6, ],[4, 5, ],]