给定一个整数数组nums和一个整数target,请你返回该数组能构成多少种不同的表达式等于target。
规则如下:
1.将数组里每个整数前面可以添加"+"或者"-"符号,组成一个表达式,例如[1,2],可以变成”+1+2","+1-2","-1+2","-1-2",这四种
2.只能添加"+"与"-"符号,不能添加其他的符号
3.如果构不成等于target的表达式,请返回0
4.保证返回的结果个数在整数范围内
数据范围:
[1,1,1,2],3
3
-1 + 1 + 1 + 2 = 3
+1 - 1 + 1 + 2 = 3
+1 + 1 - 1 + 2 = 3
[2],2
1
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ public int findTargetSumWays (int[] nums, int target) { // write code here if(nums == null || nums.length == 0) return 0; return dfs(nums, 0, target); } private int dfs(int[] nums, int index, int rest) { if(index == nums.length){ return rest == 0? 1: 0; // 到最后一个数如果rest为0了,就形成了一种合法的方案 } // 否则就给当前的数加上负号或不加负号累加到rest上,继续尝试下面的数 return dfs(nums, index + 1, rest + nums[index]) + dfs(nums, index + 1, rest - nums[index]); } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ public int findTargetSumWays (int[] nums, int target) { // write code here if(nums == null || nums.length == 0) return 0; int n = nums.length; HashMap<Integer, HashMap<Integer, Integer>> mem = new HashMap<>(); return dfs(nums, 0, target, mem); } private int dfs(int[] nums, int index, int rest, HashMap<Integer, HashMap<Integer, Integer>> mem) { if(mem.containsKey(index) && mem.get(index).containsKey(rest)) { return mem.get(index).get(rest); // 缓存命中,直接返回 } if(index == nums.length){ return rest == 0? 1: 0; // 到最后一个数如果rest为0了,就形成了一种合法的方案 } HashMap<Integer, Integer> map = new HashMap<>(); // 否则就给当前的数加上负号或不加负号累加到rest上,继续尝试下面的数 int res = dfs(nums, index + 1, rest + nums[index], mem) + dfs(nums, index + 1, rest - nums[index], mem); map.put(rest, res); mem.put(index, map); return res; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ public int findTargetSumWays (int[] nums, int target) { // write code here if(nums == null || nums.length == 0) return 0; int sum = 0; for(int i = 0; i < nums.length; i++){ sum += nums[i]; } if(sum < Math.abs(target) || ((sum + target) & 1) != 0) { // sum不足target的绝对值,或sum和target奇偶性不同,直接返回0 return 0; } int upBound = (sum + target) >> 1; int[] dp = new int[upBound + 1]; dp[0] = 1; // base case凑出0有1种方案:什么数都不选 for(int num: nums){ for(int i = upBound; i >= num; i--){ dp[i] += dp[i - num]; } } return dp[upBound]; } }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @param target int整型 # @return int整型 # class Solution: def findTargetSumWays(self , nums: List[int], target: int) -> int: # write code here if len(nums) == 0 and target == 0: return 0 res = self.traverse(nums, 0, 0, target) return res def traverse(self, nums, n, now, target): if n == len(nums) and now == target: return 1 if n >= len(nums): return 0 res = 0 res += self.traverse(nums, n + 1, now + nums[n], target) res += self.traverse(nums, n + 1, now - nums[n], target) return res
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */ int count=0; void dfs(vector<int>& nums,int id,int target,int sum) { if(id==nums.size() ){ if(sum==target) count++; // return; } else{ dfs(nums,id+1,target,sum+nums[id]); dfs(nums,id+1,target,sum-nums[id]); } } int findTargetSumWays(vector<int>& nums, int target) { // write code here if(nums.size()==0) return 0; dfs(nums,0,target,0); return count; } };
递归解题:每个数都加上正负号参与求和,如果最后的和等于target,则种类+1。
import java.util.*; public class Solution { public int findTargetSumWays (int[] nums, int target) { return func(nums, 0, target, 0); } public int func(int []nums, int index, int target, int cur) { if(index >= nums.length) return 0; int count = 0; if(cur + nums[index] == target && index == nums.length - 1) { count++; } if(cur - nums[index] == target && index == nums.length - 1) { count++; } if(index == nums.length - 1) return count; return func(nums, index + 1, target, cur + nums[index]) + func(nums, index + 1, target, cur - nums[index]); } }
package main import _"fmt" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ func findTargetSumWays( nums []int , target int ) int { if len(nums)==0{ return 0 } cnt:=0 var back_tracking func(int,int) back_tracking=func(sum int,idx int){ if idx==len(nums){ if sum==target{ cnt++ } return } back_tracking(sum+nums[idx],idx+1) back_tracking(sum-nums[idx],idx+1) } back_tracking(0,0) return cnt }
public int findTargetSumWays (int[] nums, int target) { if(nums.length==0)return 0; findT(nums,0,target); return n; } void findT(int[] nums,int i,int s){ if(i==nums.length){ if(s==0)n++; return; }else { s+=(-1)*nums[i]; findT(nums,i+1,s); s-=(-1)*nums[i]; s+=nums[i]; findT(nums,i+1,s); s-=nums[i]; } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */ int findTargetSumWays(vector<int>& nums, int target) { // write code here if(!nums.size()) return 0; return test(nums,target,nums.size()-1); } int test(vector<int>& nums,int target,int n){ //出口 if(n == -1){ if(target == 0) return 1; else return 0; } return test(nums,target - nums[n],n - 1) + test(nums,target + nums[n], n - 1); } };
class Solution: def __init__(self): self.count=0 def findTargetSumWays(self , nums: List[int], target: int) -> int: if len(nums) == 0: return 0 self.backtrack(nums, target, 0, 0) return self.count; # write code here def backtrack(self , nums: List[int], target: int, index: int, sum: int): if index == len(nums): if sum == target: self.count+=1 else : self.backtrack(nums, target, index + 1, sum + nums[index]) self.backtrack(nums, target, index + 1, sum - nums[index])
public int findTargetSumWays(int[] nums, int target) { if(nums.length==0) return 0; solve(0, nums, target); return ncount; } int ncount = 0; public void solve(int idx, int[] nums, int target) { if (idx == nums.length && target == 0) { ncount++; return; } if (idx == nums.length) return; solve(idx+1, nums, target-nums[idx]); // nums[idx]符号为正 solve(idx+1, nums, target+nums[idx]); // nums[idx]符号为负 }