蓝桥杯算法题

题目

给定一个1～N的排列a[i]，(解释：每个a[i]的值大于等于1且小于等于N，且每个a[i]的值互不相同),每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。
例如:
3 1 2 4
4 3 6
7 9
16
现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。
样例输入
4 16
样例输出
3 1 2 4

分析

这个数字三角形与杨辉三角的关系，四层杨辉三角的最后一行是1,3,3,1，本题输入4,16，输出3,1,2,4，则3x1+1x3+2x3+4x1=16，所以本题只需两个函数：求杨辉三角最后一行函数+深度搜索函数

代码

public class Main{
	static int n;
	static int sum;
	static int[] triangleLastRow=new int[n];//存放杨辉三角最后一行元素的值
	static List result=new ArrayList();//存放最终的结果
	static boolean flag = false;//是否已经完成深搜
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		sum = sc.nextInt();
		int[] used=new int[n+1];//存放某个数字是否已经用过
		triangleLastRow=triangle(n);
		dfs(0, 0,used);
	}
	
	public static int[] triangle(int n){
		int a[][]=new int[n][n];
		for(int i=0;isum)
			return ;
		if(num==n) {
			if(tempSum==sum) {
				for(int i:result){
					System.out.print(i+" ");
				}
				flag=true;
			}else {
				return ;
			}
		}
		if(!flag){
			for(int i=1;i<=n;i++){
                //未访问过标记为0，访问过标记为1
				if(used[i]==0){
					used[i] = 1;
					result.add(i);
					dfs(num+1,tempSum+triangleLastRow[num]*i,used);
					used[i] = 0;
					result.remove(result.size()-1);
				}
			}
		}
	}
}