用子集法,选or不选变成了正or负,BFS执行所有情况,判断恰好为目标和。
灵神:
设所有数的和为s,取正的和为p,则和为p-(s-p);
有t = p-(s-p) = 2p-s,即p = (s+t)/2;这里的s和t都是固定值;
这样把问题转换为了选or不选。
动态规划方程:
dfs(i, c):前i个数中恰好和为c的方案数;
选第i个,前i-1个和c-nums[i];
不选第i个,前i-1个和为c;
dfs(i, c) = dfs(i-1, c) + dfs(i-1, c-nums[i]));
暂时没看出来哪错了,,,