POJ 3187 -- Backward Digit Sums

http://poj.org/problem?id=3187
FJ and his cows enjoy playing a mental game. They write down the numbers from 1 to N (1 <= N <= 10) in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when N=4) might go like this:

    3   1   2   4  
      4   3   6  
        7   9  
         16

Behind FJ's back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number N. Unfortunately, the game is a bit above FJ's mental arithmetic capabilities.

Write a program to help FJ play the game and keep up with the cows.

http://www.hankcs.com/program/cpp/poj-3187-backward-digit-sums-challenge-programming-contest-2nd-edition-exercises-answers.html

杨辉三角前10行：

									1
								1		1
							1		2		1
						1		3		3		1
					1		4		6		4		1
				1		5		10		10		5		1
			1		6		15		20		15		6		1
		1		7		21		35		35		21		7		1
	1		8		28		56		70		56		28		8		1
1		9		36		84		126		126		84		36		9		1

杨辉三角第n层第k个数记为Ckn那么=n!/[k!(n-k)!]=n * (n – 1)…*(n – k + 1) / k!

对应着下面这段代码

1 2 3 4 5 6 7 8 9 10

int c(int n, int k) {     int result = 1;     for (int i = 0; i < k; ++i)     {         result = result * (n - i) / (i + 1);     }       return result; }

上面做了一个简化，因为原始的式子里面分子分母的项数相等所有写进一个loop里。

有了Ckn 那么即使题目中的初始数字不为1，只要乘上这个系数Ckn就行了。

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 argc, char *argv[])

{

    int N, Sum;

    cin >> N >> Sum;

    int line[16];

    int i = 0;

    for (; i < N; ++i)

    {

        line[i] = i + 1;

    }

    do 

    {

        int result = 0;

        for (i = 0; i < N; ++i)

        {

            result += c(N - 1, i) * line[i];

        }

        if (result == Sum)

        {

            break;

        }

    } while (next_permutation(line, line + N));

    copy(line, line + N, ostream_iterator<int>(cout, " "));

    return 0;

}

http://www.cnblogs.com/7hat/p/3601678.html
分析：这题用全排列的方式非常容易做。首先初始化数组为1-N，然后用STL提供的按字典序生成全排列的函数next_permutation即可枚举全排列。对于每一组数，通过计算可以知道它是否能得出已知结果。最先找到的那组数就是字典序最小的值。

15 int N, finalSum;
17 int a[MAX_N][MAX_N];                //保存序列以及计算序列结果
18 
19 int calulate(){
20     //计算序列所得的最后和
21     for(int i = 1; i < N; i ++){
22         for(int j = 0; j < N - i; j ++){
23             a[i][j] = a[i - 1][j] + a[i - 1][j + 1];
24         }
25     }
26     return a[N - 1][0];
27 }
28 
29 void solve(){
30     //初始化序列
31     for(int i = 0; i < N; i ++)
32         a[0][i] = i + 1;
33     //按字典序枚举全排列
34     do{
35         int sum = calulate();
36         if(sum == finalSum){
37             printf("%d", a[0][0]);
38             for(int i = 1; i < N; i ++){
39                 printf(" %d", a[0][i]);
40             }
41             printf("\n");
42             break;
43         }
44     }while(next_permutation(a[0], a[0] + N));
45 
46 }

http://blog.sina.com.cn/s/blog_6635898a0100kko3.html
思路：n比较小，暴搜。先由杨辉三角的性质：sum = 0Cn-1*num[0] + 1Cn-1*num[1] +``+ n-1Cn-1*num[n-1],先求出底边各个数对应的系数值，然后再暴搜枚举num[i]的值。
http://blog.csdn.net/mullerwch/article/details/38392961

1. bool visit[15];  
2. int a[15],b[15];  
3. int N, sum;  
4.   
5. bool per(int k){  
6.     if(k == (N+1)){  
7.         int i,j;  
8.         for(i=1; i<=N; ++i)  
9.             b[i] = a[i];  
10.         for(i=1; i<N; ++i){  
11.             for(j=1; j<=N-i; ++j){  
12.                 b[j] = b[j]+b[j+1];  
13.             }  
14.         }  
15.         if(b[1] == sum){  
16.             for(i=1; i<=N; ++i)  
17.                 printf("%d ", a[i]);  
18.             printf("\n");  
19.             return true;  
20.         }  
21.         return false;  
22.     }  
23.   
24.     int i;  
25.     for(i=1; i<=N; ++i){  
26.         if(!visit[i]){  
27.             visit[i] = true;  
28.             a[k] = i;  
29.             if(per(k+1))  
30.                 return true;  
31.             visit[i] = false;  
32.         }  
33.     }  
34.     return false;  
35. }  
36. int main(){  
37.     #ifdef LOCAL  
38.         freopen("1.in","r", stdin);  
39.     #endif  
40.   
41.     while(~scanf("%d%d", &N, &sum)){  
42.         memset(visit, false, sizeof(visit));  
43.         per(1);  
44.     }  
45.     return 0;  
46. }  

Read full article from 3187 -- Backward Digit Sums