Factor Combinations - Tổ hợp thừa số của số nguyên

Cho số nguyên n, tìm tất cả tổ hợp thừa số (không tính 1 và n). Ví dụ: 12 → [[2,6],[2,2,3],[3,4]].

Giải thuật (Backtracking)

Đệ quy từ start=2 đến sqrt(n). Nếu i chia hết n, thêm i vào tổ hợp, đệ quy với n/i bắt đầu từ i. Khi n==1 trả về. Loại trừ tổ hợp chỉ có n ban đầu.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> v) {
    cout << "[";
    for (auto& row : v) {
        cout << "[";
        for (int x : row) cout << x << ", ";
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<vector<int>> solve(int n, int target, int start) {
        vector<vector<int>> ret;
        if (n == 1) return ret;
        if (n != target) ret.push_back({n});
        for (int i = start; i * i <= n; i++) {
            if (n % i == 0) {
                auto other = solve(n / i, target, i);
                for (auto& comb : other) {
                    comb.push_back(i);
                    ret.push_back(comb);
                }
            }
        }
        return ret;
    }

    vector<vector<int>> getFactors(int n) {
        return solve(n, n, 2);
    }
};

int main() {
    Solution ob;
    print_vector(ob.getFactors(16));
    return 0;
}

Đầu vào

16

Đầu ra

[[8, 2, ],[4, 2, 2, ],[2, 2, 2, 2, ],[4, 4, ],]