題目描述
給定一個非負整數陣列，a1, a2, …, an, 和一個目標數，S，現在你有兩個符號 + 和 -，對于陣列中的任意一個整數，你都可以從 + 或 -中選擇一個符號添加在前面，
回傳可以使最終陣列和為目標數 S 的所有添加符號的方法數，
示例：
輸入：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，
提示：
陣列非空，且長度不會超過 20 ，
初始的陣列的和不會超過 1000 ，
保證回傳的最終結果能被 32 位整數存下，
AC代碼：
class Solution {
public:
void recur(vector<int>& nums,int n,int S,int sum,int step,int &ans){
if(n==step){
ans+=sum+nums[step]==S;
ans+=sum-nums[step]==S;
return;
}
recur(nums,n,S,sum+nums[step],step+1,ans);
recur(nums,n,S,sum-nums[step],step+1,ans);
return;
}
int findTargetSumWays(vector<int>& nums, int S) {
int n=nums.size()-1;
int ans=0;
recur(nums,n,S,0,0,ans);
return ans;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/22033.html
標籤：java
上一篇：視頻超分：TDAN（TDAN: Temporally Deformable Alignment Network for Video Super-Resolution)