POJ 3187 Backward Digits Sums
There are 1 to \(N\) digits (\(1\le N \le 10\)) in certain order. Add adjacent numbers together to get the next line, until the there is only one number left.(Just like Pascal’s triangle) For example, there are 3 integers: $$ 1, 2, 3 $$ $$ 3, 5 $$ $$ 8 $$
So, given \(N\) and the final sum, find the lexicographically least ordering of integers.
Link: http://poj.org/problem?id=3187
Notes:
Be aware of that the question is asking 1 to \(N\) digits, so we don’t have to test all possible permutations from 1 to 10.
The results of
next_permutation()
in STL are in ascending order in default.
Solution:
Use next_permutation()
to check all possibilities and stimulate the triangle additions. Since the permutation is already in lexicographical order, when we get the find the first result, it is the final answer.

