描述
給定一個非負整數的串列a1,a2,…an，再給定一個目標S，現在用+和-兩種運算，對于每一個整數，選擇一個作為它前面的符號，
找出有多少種方法，使得這些整數的和正好等于S，
說明
1、給定陣列的長度是正整數而且不會超過20，
2、所有元素的和不會超過1000，
3、輸出結果一定在32位整數范圍內，
樣例
- 例1:
輸入: nums為 [1, 1, 1, 1, 1], S 為 3.
輸出: 5
解釋:
-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 = 3
有5種方法讓和為3.
- 例2:
輸入: nums 為 [], S 為 3.
輸出: 0
解釋:
沒有方法能讓和為3
決議
var findTargetSumWays = function(nums, S) {
if (nums == null || nums.length == 0) return 0;
var sums = 0;
nums.forEach(num => sums += num);
if (sums < S || (S + sums) % 2 == 1) return 0;
var p = (S + sums) >> 1;
var dp = new Array(p + 1).fill(0);
dp[0] = 1;
nums.forEach(num => {
for (var i = p; i >= num; i--) {
dp[i] += dp[i - num];
}
})
return dp[p];
};
運行結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/72938.html
標籤：其他