You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5Explanation: -1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
The length of the given array is positive and will not exceed 20.The sum of elements in the given array will not exceed 1000.Your output answer is guaranteed to be fitted in a 32-bit integer.
Subscribe to see which companies asked this question.
【問題分析】
1、該問題求解數(shù)組中數(shù)字只和等于目標(biāo)值的方案個數(shù)，每個數(shù)字的符號可以為正或負(fù)(減整數(shù)等于加負(fù)數(shù))。
2、該問題和矩陣鏈乘很相似，是典型的動態(tài)規(guī)劃問題
3、舉例說明: nums = {1,2,3,4,5}, target=3, 一種可行的方案是+1-2+3-4+5 = 3
     該方案中數(shù)組元素可以分為兩組，一組是數(shù)字符號為正(P={1,3,5})，另一組數(shù)字符號為負(fù)(N={2,4})
     因此: sum(1,3,5) - sum(2,4) = target
              sum(1,3,5) - sum(2,4) + sum(1,3,5) + sum(2,4) = target + sum(1,3,5) + sum(2,4)
              2sum(1,3,5) = target + sum(1,3,5) + sum(2,4)
              2sum(P) = target + sum(nums)
              sum(P) = (target + sum(nums)) / 2
     由于target和sum(nums)是固定值，因此原始問題轉(zhuǎn)化為求解nums中子集的和等于sum(P)的方案個數(shù)問題
4、求解nums中子集合只和為sum(P)的方案個數(shù)(nums中所有元素都是非負(fù))
      該問題可以通過動態(tài)規(guī)劃算法求解
      舉例說明：給定集合nums={1,2,3,4,5}, 求解子集，使子集中元素之和等于9 = new_target = sum(P) = (target+sum(nums))/2
              定義dp[10]數(shù)組, dp[10] = {1,0,0,0,0,0,0,0,0,0}
              dp[i]表示子集合元素之和等于當(dāng)前目標(biāo)值的方案個數(shù), 當(dāng)前目標(biāo)值等于9減去當(dāng)前元素值
              當(dāng)前元素等于1時，dp[9] = dp[9] + dp[9-1]
                                            dp[8] = dp[8] + dp[8-1]
                                            ...
                                            dp[1] = dp[1] + dp[1-1]
              當(dāng)前元素等于2時，dp[9] = dp[9] + dp[9-2]
                                            dp[8] = dp[8] + dp[8-2]
                                            ...
                                            dp[2] = dp[2] + dp[2-2]
              當(dāng)前元素等于3時，dp[9] = dp[9] + dp[9-3]
                                            dp[8] = dp[8] + dp[8-3]
                                            ...
                                            dp[3] = dp[3] + dp[3-3]
              當(dāng)前元素等于4時，
                                            ...
              當(dāng)前元素等于5時，
                                           ...
                                           dp[5] = dp[5] + dp[5-5]
             最后返回dp[9]即是所求的解
【AC代碼】
class Solution {    public:        int findTargetSumWays(std::vector<int>& nums, int S) {            int sum = std::accumulate(nums.begin(), nums.end(), 0);            return sum < S || (S + sum) & 1 ? 0 : subsetSum(nums, (S+sum) >> 1);        }        int subsetSum(std::vector<int>& nums, int s) {            int dp[s+1];            memset(dp, 0, sizeof(int)*(s+1));            dp[0] = 1;            for(int n: nums) {                for (int i = s; i >= n; --i) {                    dp[i] += dp[i-n];                }            }            return dp[s];        }};
參考內(nèi)容:
https://discuss.leetcode.com/topic/76243/java-15-ms-c-3-ms-o-ns-iterative-dp-solution-using-subset-sum-with-explanation/2
https://discuss.leetcode.com/topic/63049/my-simple-c-dp-code-with-comments/2