找两个不重叠subsequence它们sum一样

不知道在哪里看到的题
从一个数组里 问是否存在两个不重叠的subsequence使得他们的 sum一样
比如
10 3 6 2 1 1 4 5
那么就存在
比如
10 和
6 4
它们的sum就是一样的
求大神指点一波


补充内容 (2019-10-17 07:28):
目前只能想到bruteforce  但是是指数的复杂度，。

LC956. Tallest Billboard

闻着有股dp的味

我能想到两个解法，都是指数级
1. bruteforce， 用两个bucket存sum。每个数字三个选项，进第一个bucket，进第二个bucket，都不进。选完了看下是不是符合。复杂度O(3^n)。可以用剩余最大／最小累计和做适当的剪枝。
2. a＋b＋c ＝ d ＋ e 也就是 a ＋ b ＋ c － d － e ＝ 0。只要我们找到一个序列，给其中数字加上正负号（至少一个正号，至少一个负号），和等于0就行。用两个hash set。一个记载可能出现的全正序列和，记为set1，一个记载可能出现的至少有一个为负（不能都为负）的序列和。记为set2。一个数字一个数字来，如果当前数字a存在在set1中，我们找到了一个解。如果a或者－a在set2中我们也找到了一个解。直接返回true就行。否则update 连个set。对于set1里面的元素b，把（a＋b）加入set1里，把（b－a）加入set2里。对于set2里的元素c，把（c ＋ a）和 （c － a）加入set2里。复杂度O(2^n) * O(n). 因为set里的不同数目最多就2^n个。

两个解法都是可以解决含有负数的输入。
不知道第二个算法对不对，欢迎讨论。。