试题 算法训练 数字游戏 java 题解 228

问题描述

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

输入格式

第1行为两个正整数n，sum

输出格式

一个1～N的一个排列

样例输入

4 16

样例输出

3 1 2 4

数据规模和约定

0<n<=10

解题思路：

欲求最初的序列，并且是符合条件的最小序列。可以将所求序列全排列，当每排好一种情况时，则进行累加求和，为了不改变原始数组中的值，需要拷贝一个数组，判断累加和是否等于题给出的和，满足时输出该数组并退出即可。

全排列问题：

全排列问题https://blog.csdn.net/weixin_48898946/article/details/121589155

注意在拷贝数组时，不能用list，因为用list涉及到list的替换元素（set方法），而初始时，list中为空，第一次替换会下标越界（事实上，即使提前处理使得不越界也会超时）。而如果每次都开一个list，对时间和空间都会产生很大代价。由于第五个测试点没有符合条件的解，意味着需要将所有全排列的数都每次开list，所以会超时。所以拷贝数组用一个常规一维数组就行。

java代码：

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int n = Integer.parseInt(split[0]);
		int sum = Integer.parseInt(split[1]);
		Temp228 temp = new Temp228(n, sum);
		temp.dfs(1);
	}
}
class Temp228{
	int n;
	int sum;
	boolean visited[];//标志数字是否出现过，避免重复出现
	List<Integer> list = new ArrayList<>();//存放实时数据
	int []arr;//便于筛选时的拷贝数组
	
	public Temp228(int n, int sum) {
		this.n = n;
		this.sum = sum;
		visited = new boolean[n + 1];
		arr = new int[n];
	}
	
	public void dfs(int step) {
		if(step > n) {
			if(compare()) {//当都排列好时，就进行符合条件的筛选
				System.exit(0);//选好直接退出程序
			}
			return;
		}
		for(int i = 1; i <= n; i++) {
			if(!visited[i]) {
				visited[i] = true;
				list.add(i);
				dfs(step + 1);
				visited[i] = false;//回溯
				list.remove(list.size() - 1);
			}
		}
	}
	
	public boolean compare() {
		for(int i = 0; i < list.size(); i++) {
			arr[i] = list.get(i);//拷贝数据
		}
		for(int i = 1; i < n; i++) {//计算相加后的“左下角”值
			for(int j = 1; j <= n - i; j++) {
				arr[j - 1] = arr[j] + arr[j - 1];
			}
		}
		if(arr[0] == sum) {//符合条件时，直接打印并返回true
			for(int i = 0; i < list.size() - 1; i++) {
				System.out.print(list.get(i) + " ");
			}
			System.out.print(list.get(list.size() - 1));
			return true;
		}
		return false;
	}
}

提交截图：