Trong bài toán này, chúng ta cho hai số n và tổng. Ta phải in ra tất cả các số có n chữ số mà tổng của chúng bằng tổng. Trong bài toán này, các số có số 0 đứng đầu không được xem xét.
Hãy lấy một ví dụ để hiểu vấn đề,
Input: n = 2 , sum = 5 Output: 14 23 32 41 50 Explanation: The sum of digits of the number in all numbers in 5.
Để giải quyết vấn đề này, chúng ta sẽ phải tìm tất cả các số có n chữ số với tổng bằng giá trị tổng đã cho. Đối với điều này, chúng tôi sẽ cố định một vị trí chữ số với tất cả các giá trị và dựa trên vị trí của nó là chẵn hay lẻ, gọi các giá trị ở các vị trí khác trong số sao cho điều kiện vẫn được thỏa mãn.
Ví dụ
Chương trình thực hiện giải pháp trên -
#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;
} Đầu ra
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