In Tất Cả Số N Chữ Số Có Tổng Chữ Số Bằng Tổng Cho Trước Trong C++

Trong bài toán này, chúng ta được cho hai số n và sum. In tất cả số N chữ số có tổng chữ số bằng sum cho trước. Các số có 0 dẫn đầu không được coi.

Ví dụ để hiểu vấn đề:

Đầu vào: n = 2, sum = 5 → Đầu ra: 14 23 32 41 50
Giải thích: Tổng chữ số của tất cả các số là 5.

Để giải quyết, ta tìm tất cả số N chữ số có tổng bằng giá trị cho trước. Cố định một vị trí chữ số với mọi giá trị và dựa trên vị trí chẵn/lẻ, gọi đệ quy cho các vị trí khác sao cho điều kiện vẫn thỏa mãn.

Ví Dụ

Chương trình triển khai giải pháp:

#include <iostream>
using namespace std;

void PrintNumberWithDigitSum(int n, int sum, char* out, int index) {
    if (index > n || sum < 0)
        return;
    if (index == n) {
        if (sum == 0) {
            out[index] = ' ';
            cout << out << " ";
        }
        return;
    }
    for (int i = 0; i <= 9; i++) {
        out[index] = i + '0';
        PrintNumberWithDigitSum(n, sum - i, out, index + 1);
    }
}

void numberWithSum(int n, int sum) {
    char out[n + 1];
    for (int i = 1; i <= 9; i++) {
        out[0] = i + '0';
        PrintNumberWithDigitSum(n, sum - i, out, 1);
    }
}

int main() {
    int n = 3, sum = 6;
    cout << "Tất cả số " << n << " chữ số có tổng " << sum << " là:\n";
    numberWithSum(n, sum);
    return 0;
}

Đầu Ra

Tất cả số 3 chữ số có tổng 6 là: 105 114 123 132 141 150 204 213 222 231 240 303 312 321 330 402 411 420 501 510 600