涉及知识点：动态规划，类背包问题
思路一：问题可以转化成：给定 nn n 个正整数，计算从中选出若个数字组合，每个数字可以加或者减，最终能得到多少种正整数结果。
状态定义：dp(i,j) dp(i,j) dp(i,j) 表示前i i i 个数字选择若干个加或者减，能否获得和为j j j 。(−105≤j≤105 -10^5\le j \le 10^5 −105≤j≤105 )状态转移方程：dp(i,j)=dp(i−1,j)∣dp(i−1,j−a[i])∣dp(i−1,j+a[i]) dp(i,j) = dp(i-1,j) | dp(i-1, j-a[i]) | dp(i-1,j+a[i]) dp(i,j)=dp(i−1,j)∣dp(i−1,j−a[i])∣dp(i−1,j+a[i]) 。初始状态：dp(0,0)=1 dp(0,0) = 1 dp(0,0)=1 。时间复杂度分析：状态数n∗sum∗2 n* sum * 2 n∗sum∗2 ，状态转移方程复杂度O(1) O(1) O(1) ，总时间复杂度O(n∗sum) O(n*sum) O(n∗sum) ，sum sum sum 表示所有数总和的最大值为105 10^5 105 。思路二：问题还可以转化成：给定 2 ∗ n2*n 2∗n 个正整数，a0 ,a1 , . . . ,an , −a0 , −a1 , . . . , −ana_0,a_1,...,a_n,-a_0,-a_1,...,-a_n a0,a1,...,an,−a0,−a1,...,−an ，每个数字可以选或者不选，问相加可以组合成多少种不同的正整数。这样就是一个经典的01背包问题了，只要注意一下负数问题即可。
其它技巧注意事项：
利用滚动数组，反复交换cur cur cur 和pre pre pre 来节约空间。使用offset offset offset 偏移来保证dp dp dp 过程中可以记录获取负数重量的可能性，以便后续转移。