POJ 3187 Backward Digit Sums 题解 《挑战程序设计竞赛》

题目：POJ 3187

思路：

这道题很简单，用next_permutation枚举1~N的所有排列，然后依次相加，判断最后的和是否等于sum，是的话则break，即为字典序最前的。

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int sum;
int mycase[11][11];

int main() {
    cin >> n >> sum;
    for (int i = 1; i <= n; i++) {
        mycase[n][i] = i;
    } 
    do {
        for (int i = n; i > 1; i--) {
            for (int j = 1; j < i; j++) {
                mycase[i - 1][j] = mycase[i][j] + mycase[i][j + 1];
            }
        }
        if (mycase[1][1] == sum) {
            for (int i = 1; i <= n; i++) {
                cout << mycase[n][i] << " ";
            }
            break;
        }
    } while (next_permutation(mycase[n] + 1, mycase[n] + 1 + n));
    return 0;
}

 注意：

• next_permutaiton()的两个参数分别是枚举起始的元素，和结束的元素的后一个元素。