Hãy xem xét chúng ta phải tạo ra tất cả các kết hợp có thể có của k số cộng lại với một số n, với điều kiện chỉ có thể sử dụng các số từ 1 đến 9. Mỗi kết hợp phải là một bộ số duy nhất. Tất cả các số phải là số dương và giải pháp không được chứa các kết hợp trùng lặp. Vì vậy, nếu k =3 và n =9, thì các kết hợp có thể có là [[1,2,6], [1,3,5], [2,3,4]]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Giả sử chúng ta sẽ giải quyết vấn đề này bằng cách hình thành một phương pháp có tên là giải. Đây sẽ là phương thức đệ quy, điều này sẽ nhận k, n, mảng tạm thời và bắt đầu. khởi đầu ban đầu là 1
- nếu n =0
- nếu kích thước của temp =k, sau đó chèn tạm thời vào res và trả về
- for i:=bắt đầu đến tối thiểu là 9 và n
- chèn tôi vào tạm thời
- giải quyết (k, n - i, tạm thời, i + 1)
- xóa phần tử cuối cùng khỏi tạm thời
- Phương thức chính sẽ giống như
- tạo một vectơ trống được gọi là tạm thời
- giải quyết (k, n, tạm thời)
- trả lại res
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
3 9
Đầu ra
[[1, 8, ],[2, 7, ],[3, 6, ],[4, 5, ],]