poj 3187 三角数问题

题意：给你两个数，一个n表示这个三角有多少层，一个sum表示总和

思路：

    类似杨辉三角 

               1

           1       1

         1      2     1

第n行的第k个数 为 n!/k!(n-k)!

1. 暴力枚举，因为杨辉三角每行的第一个数都是1，所以你需要每行都乘上一个系数
2. 排列系数

解决问题的代码：

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
int c(int n, int k)
{
    int result = 1;
    for (int i = 0; i < k; i++)
        result = result * (n - i) / (i + 1);
    return result;
}
int main()
{
    int n, sum;
    int line[16];
    scanf("%d%d", &n, &sum);
    for (int i = 0; i < 16; i++)
        line[i] = i + 1;
    do {
        int result = 0;
        for (int i = 0; i < n; i++)
            result += c(n - 1, i)*line[i];
        if (result == sum)
            break;
    } while (next_permutation(line, line + n));
    for (int i = 0; i < n; i++)
        printf("%d ", line[i]);
    printf("
");
    return 0;
}