Question

一到水题求思路

刚开始刷 ACM，现在大一上刚结束。刷题有些不会的，求解答。
Description

在如图1所示的数字宝塔中，从最顶层走到最底层，
每次只能走到下一层的左边或右边的数字。
求出使其所经过的所有数字之和为SUM的路径。

Input

有多组测试，
每组首先输入如图1所示结构的一个数字宝塔，
共九行（1~9），第i行有i个自然数。
第十行输入一个自然数SUM。

Output

输出描述所述的路径，输出格式如样例。
多个答案的输出顺序按先向左走再向右走决定。

Sample Input
74 66 9 36 3 7 12 5 3 2 85 9 4 7 3 26 4 1 8 5 6 33 9 7 6 8 4 1 52 5 7 3 5 7 8 4 260
Sample Output
7->4->9->7->3->7->8->8->77->6->9->7->3->7->8->8->5
不需要完整代码，就求告诉算法和走左走右的方法

若以下回答无法解决问题，邀请你更新回答

Answer 1

能发个题目的链接吗？我想试试

追问

http://acm.nbu.edu.cn/v1.0/Problems/Problem.php?pid=2408

追答

#include <stdio.h>
int a[9][9];
int path[10],sum;
void output()
{
    for(int i=0;i<8;i++)
        printf("%d->",path[i]);
    printf("%d\n",path[8]);
}
void dfs(int x,int y,int now)
{
    if(now>sum)
       return ;
    if(x==9)
    {
        if(now==sum)
            output();

            return;
    }

    path[x]=a[x][y];
    dfs(x+1,y,a[x][y]+now);
    if(x!=8)
    dfs(x+1,y+1,a[x][y]+now);

}
int main( )
{
while(scanf("%d",&a[0][0])!=EOF)
{
    for(int i=1;i<=8;i++)
        for(int j=0;j<=i;j++)
        scanf("%d",&a[i][j]);
        scanf("%d",&sum);
        dfs(0,0,0);
}


    return 0;
}
直接搜索就好！