พิมพ์ตัวเลข N หลักที่ผลรวมหลักเท่ากับค่าที่กำหนดใน C++

ภาพรวมปัญหา

ได้รับ n (จำนวนหลัก) และ sum (ผลรวมที่ต้องการ) ต้องพิมพ์ตัวเลข N หลักที่ผลรวมหลัก = sum (ไม่นับ leading zeros)

ตัวอย่าง

Input: n = 2, sum = 5
Output: 14 23 32 41 50

วิธีแก้ปัญหา (Recursion + Backtracking)

1. กำหนดหลักแรก 1-9 (ไม่ให้เป็น 0)
2. หลักที่เหลือ 0-9
3. Recursive ลด sum ตามหลักที่เลือก จนครบ n หลัก

ตัวอย่างโค้ด C++

#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 << "All " << n << " digit numbers with sum " << sum << " are:\n";
    numberWithSum(n, sum);
    return 0;
}

ผลลัพธ์ (Output)

All 3 digit numbers with sum 6 are:
105 114 123 132 141 150 204 213 222 231 240 303 312 321 330 402 411 420 501 510 600