2023-07-02：给定一个1~N的排列，每次将相邻两数相加，可以得到新的序列，长度是N-1

再对新的序列，每次将相邻两数相加，可以得到新的序列，长度是N-2

这样下去可以最终只剩一个数字

比如 :

3 1 2 4

4 3 6

7 9

16

现在如果知道N，和最后的数字sum，反推最原始的序列是什么

如果有多个答案，返回字典序最小的那个

字典序看做所有数字拼起来的字符串字典序

比如

1, 10, 2... 拼起来是 1102...

1, 2, 3, 4... 拼起来是 1234...

认为 1, 10, 2...的字典序更小

如果给定的n和sum，有答案，返回一个N长度的答案数组

如果给定的n和sum，无答案，返回一个1长度的数组{ -1 }

输入 : N = 4, sum = 16

输出 : 3 1 2 4

输入 : N = 10, sum = 4116

输出 : 1 3 5 7 10 9 8 6 4 2

答案2023-07-02：

大体步骤如下：

1.创建一个二维动态数组dp，大小为(1<<(n+1))x(sums[n]+1)。

2.定义一个变量status，其初始值为((1 << (n + 1)) - 1) ^ 1。

3.如果n小于1或大于10，或者sum大于sums[n]，则返回数组[-1]。

4.调用process函数处理状态status、剩余和rest、索引index、长度n、模数组modulus和动态数组dp，得到结果ans。

5.如果ans的值为-1，说明无法找到合适的序列，返回数组[-1]。

6.创建一个长度为n的答案数组ans，并初始化index为0，rest为sum。

7.当status不等于0时，执行以下循环：

• 将dp[status][rest]的值赋给ans[index]。

• 将status异或上1 << ans[index]，更新status。

• 将rest减去ans[index] * modulus[index]，更新rest。

• 将index加1。

8.返回答案数组ans。

总的时间复杂度：O(2^N * sum)，其中N为输入的n，sum为输入的sum。
总的空间复杂度：O(2^N * sum)，包括二维动态数组dp的空间。

go语言代码如下：

package main

import "fmt"

var moduluses = [][]int{
	{},
	{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},
}

var sums = []int{0, 1, 3, 9, 24, 61, 148, 350, 808, 1837, 4116}

func lsp(n int, sum int) []int {
	if n < 1 || n > 10 || sum > sums[n] {
		return []int{-1}
	}
	dp := make([][]int, 1<<(n+1))
	for i := range dp {
		dp[i] = make([]int, sums[n]+1)
	}
	status := ((1 << (n + 1)) - 1) ^ 1
	if !process(status, sum, 0, n, moduluses[n], dp) {
		return []int{-1}
	}
	ans := make([]int, n)
	index := 0
	rest := sum
	for status != 0 {
		ans[index] = dp[status][rest]
		status ^= 1 << ans[index]
		rest -= ans[index] * moduluses[n][index]
		index++
	}
	return ans
}

func process(status int, rest int, index int, n int, modulus []int, dp [][]int) bool {
	if rest < 0 {
		return false
	}
	if status == 0 {
		return rest == 0
	}
	if dp[status][rest] != 0 {
		return dp[status][rest] != -1
	}
	ans := -1
	if n == 10 && (status&(1<<10)) != 0 {
		if process(status^(1<<10), rest-modulus[index]*10, index+1, n, modulus, dp) {
			ans = 10
		}
	}
	if ans == -1 {
		for i := 1; i <= n; i++ {
			if (status & (1 << i)) != 0 {
				if process(status^(1<<i), rest-modulus[index]*i, index+1, n, modulus, dp) {
					ans = i
					break
				}
			}
		}
	}
	dp[status][rest] = ans
	return ans != -1
}

func main() {
	N1 := 4
	sum1 := 16
	ans1 := lsp(N1, sum1)
	for _, num := range ans1 {
		fmt.Printf("%d ", num)
	}
	fmt.Println()

	N2 := 10
	sum2 := 4116
	ans2 := lsp(N2, sum2)
	for _, num := range ans2 {
		fmt.Printf("%d ", num)
	}
	fmt.Println()

	N3 := 10
	sum3 := 3688
	ans3 := lsp(N3, sum3)
	for _, num := range ans3 {
		fmt.Printf("%d ", num)
	}
	fmt.Println()

	N4 := 10
	sum4 := 4013
	ans4 := lsp(N4, sum4)
	for _, num := range ans4 {
		fmt.Printf("%d ", num)
	}
	fmt.Println()
}