给定一个整数数组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
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]; } }
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]; } }
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]符号为负 }