[Quay Lui - Nhánh Cận]. Bài 30. Phân hoạch 2

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

28Tech

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một số nguyên dương N và hãy liệt kê tất cả các phân hoạch biểu diễn N dưới dạng tổng các số tự nhiên nhỏ hơn hoặc bằng nó.

Ví dụ với 4 bạn có 8 cách biểu diễn :

1 1 1 1, 1 1 2, 1 2 1 , 1 3, 2 1 1, 2 2, 3 1, 4

Đầu vào

Dòng duy nhất chứa N

Giới hạn

1<=N<=15

Đầu ra

Dòng 1 in ra số cách biểu diễn
Các dòng tiếp theo in ra các cách biểu diễn theo thứ tự tăng dần về từ điển

Ví dụ :

Input 01

Output 01

Bình luận

Hãy đọc nội quy trước khi bình luận.

bengokyeuanh99 đã bình luận lúc 24, Tháng 8, 2025, 14:19

Full AC

include <iostream>

include <vector>

class PartitionGenerator { public: explicit PartitionGenerator(int n) : n(n) { seq.reserve(n_); }

void run() {
    std::cout << (1LL << (n_ - 1)) << '\n';
    dfs(n_);
}

private: int n; std::vector<int> seq;

void dfs(int remain) {
    if (remain == 0) {
        print();
        return;
    }
    for (int x = 1; x <= remain; ++x) {
        seq_.push_back(x);
        dfs(remain - x);
        seq_.pop_back();
    }
}

void print() const {
    for (size_t i = 0; i < seq_.size(); ++i) {
        if (i) std::cout << ' ';
        std::cout << seq_[i];
    }
    std::cout << '\n';
}

};

int main() { std::ios::syncwithstdio(false); std::cin.tie(nullptr);

int n;
std::cin >> n;
PartitionGenerator(n).run();
return 0;

}

0
nduc1907 đã bình luận lúc 24, Tháng 8, 2025, 13:41
hihihi~hi~$$hi$$hihi

hi`hi

hi

hi## hi

hi

##

`