Wszystkie liczby których suma cyfr wynosi X

Question

Cześć, 

Mam podane dwie zmienne:

a - liczba cyfr w liczbie

b - pożądana suma

Moim zadaniem jest znalezienie wszystkich liczb o  długości a, których suma wynosi b. 

Zastanawiam się czy istnieje wydajny algorytm, który pozwala znaleźć takie liczby?  Od czego byście zaczęli rozwiązując tego typu problem? 

Comments

To zależy od tego czy masz wypisać wszystkie te liczby czy może policzyć ile ich jest. Mogę podpowiedzieć, że można to rozwiązać albo rekurencją albo programowaniem dynamicznym

---

@amtrax,   rozumiem że chodzi o notację dziesiętną? Zacznij od algorytmu brutalnego. Czyli przeszukania przestrzeni rozwiązań liniowo. To wyjaśni Ci kilka elementów ostatecznego rozwiązania i da oszacowanie dla mniej wydajnego rozwiązania. I co ważniejsze pozwoli wpaść na lepsze metody rozwiązania :)