【问题】牛客刷到一道题，没思路

2022/4/13镜像同步24 回复

给定一个数组a，长度为n，1<=n<=100,1<=a[i]<=100，问能否找到两个子序列，他们的和相等，如果能找到，分别输出两个子序列，如果不能，输出-1。能不能找到等和子序列，这个我用dp解决了，但是怎么输出这两个子序列没啥思路，难不成用回溯？但是回溯的时间复杂度有点高啊。。。[ema1]

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

specops机器人#1 · 2022/4/13

背包问题追踪解

brz222机器人#2 · 2022/4/13

【在 specops 的大作中提到: 】 : 背包问题追踪解老哥能不能讲的详细一点，弱鸡搞不懂啊[ema1]

a912655391机器人#3 · 2022/4/13

Dp数组里面保存上一个元素的下标试试？

superheart机器人#4 · 2022/4/13

开一个和dp数组长度一样的数组，每个位置记录当前状态是从哪一个状态转移过来的

brz222机器人#5 · 2022/4/14

【在 a912655391 的大作中提到: 】 : Dp数组里面保存上一个元素的下标试试？有思路了，感谢老哥提醒

brz222机器人#6 · 2022/4/14

【在 superheart 的大作中提到: 】 : 开一个和dp数组长度一样的数组，每个位置记录当前状态是从哪一个状态转移过来的懂了懂了，感谢老哥

liu487639机器人#7 · 2022/4/14

这样只能拿一组解，如果要全部的解呢【在 a912655391 的大作中提到: 】 : Dp数组里面保存上一个元素的下标试试？

superheart机器人#8 · 2022/4/14

【在 liu487639 的大作中提到: 】 : 这样只能拿一组解，如果要全部的解呢那样只能回溯剪枝了

liu487639机器人#9 · 2022/4/14

我想到一种数据结构，跳表，可行性还需要验证【在 superheart 的大作中提到: 】 : 那样只能回溯剪枝了