Tổng kết hợp III trong C++

Giả sử chúng ta phải tạo tất cả các tổ hợp có thể của k số cộng thành số n, cho rằng chỉ có thể sử dụng các số từ 1 đến 9. Mỗi tổ hợp nên là một tập hợp duy nhất các số. Tất cả các số phải dương, và giải pháp không được chứa các tổ hợp trùng lặp. Vì vậy, nếu k = 3 và n = 9, thì các tổ hợp có thể là [[1,2,6],[1,3,5],[2,3,4]]

Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:

• Giả sử chúng ta sẽ giải quyết bằng cách tạo một phương thức gọi là solve. Đây sẽ là phương thức đệ quy, nhận k, n, mảng tạm, và start. start ban đầu là 1
• nếu n = 0
  • nếu kích thước mảng tạm = k, thì chèn mảng tạm vào kết quả và trả về
  • for i := start đến min của 9 và n
    • chèn i vào mảng tạm
    • solve(k, n – i, mảng tạm, i + 1)
    • xóa phần tử cuối cùng khỏi mảng tạm
• Phương thức chính sẽ như sau
  • tạo một vector rỗng gọi là mảng tạm
  • solve(k, n, mảng tạm)
  • trả về kết quả

Hãy xem 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, ],]