# POJ 3187 Backward Digits Sums

Contents

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.

### 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.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include using namespace std; int n, sum, ans[11], s[11]; void solve() { for (int i = 1; i <= n; i++) ans[i-1] = i; if (n == 1 && ans[0] == sum) { cout << sum << endl; return; } do { for (int i = 0; i < n-1; i++) s[i] = ans[i]+ans[i+1]; for (int i = n-2; i >= 0; i--) { for (int j = 0; j < i; j++) s[j] = s[j]+s[j+1]; } if (s[0] == sum) { for (int i = 0; i < n; i++) cout << ans[i] << " "; cout << endl; return; } } while (next_permutation(ans, ans+n)); } int main(void) { cin >> n >> sum; solve(); return 0; }