本文共 1956 字，大约阅读时间需要 6 分钟。

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意

一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

1、常规思路 

对于数组中的每一个数，它的符号只有两种选择，一种是取正，一种是取负，根据这两种策略，计算结果。

int ncount = 0;	public void solve(int idx, int[] nums, int S)	{//		if (S < 0) // 这个边界条件不合适，它会影响结果//			return;		if (idx == nums.length && S == 0) // 找到了一个解		{			ncount++;			return;		}				if (idx == nums.length) 			return;				solve(idx+1, nums, S-nums[idx]); // nums[idx]符号为正		solve(idx+1, nums, S+nums[idx]); // nums[idx]符号为负	}	    public int findTargetSumWays(int[] nums, int S)     {    	solve(0, nums, S);    	return ncount;    }

2、记忆化搜索

public int solve(int idx, int[] nums, int S, Map
   
     map)	{		// 避免数字重复，无法找到截断点		String encodeString = idx + "->" + S;				if (map.containsKey(encodeString))			return map.get(encodeString);				if (idx == nums.length)		{			return S == 0 ? 1 : 0; // S==0找到一个解		}				int curNum = nums[idx];		int positive = solve(idx+1, nums, S-nums[idx], map);		int negitive = solve(idx+1, nums, S+nums[idx], map);		map.put(encodeString, positive+negitive);		return positive + negitive;	}	    public int findTargetSumWays(int[] nums, int S)     {    	HashMap
    
      hashMap = new HashMap
     
      ();    	if (nums == null || nums.length == 0)    		return 0;    	return solve(0, nums, S, hashMap);    }
     
    
   

3、动态规划

public int findTargetSumWays(int[] nums, int S)     {    	int sum = 0;    	if (nums == null || nums.length == 0)    		return 0;    	    	// 计算数组中元素之和    	for (int i = 0; i < nums.length; i++)    		sum += nums[i];    	if (S > sum || (sum + S) % 2 == 1)    		return 0;    	return solve(nums, (sum+S)/2);    }        int solve(int[] nums, int S)	{    	int[] dp = new int[S+1]; // 状态矩阵    	dp[0] = 1;     	/*    	 递归式    	solve(idx+1, nums, S-nums[idx]); // nums[idx]符号为正		solve(idx+1, nums, S+nums[idx]); // nums[idx]符号为负		*/    	for (int i=0; i
   
    =nums[i]; j--)    		{    			dp[j] += dp[j-nums[i]];    		}    	}		return dp[S];	}
   

转载地址：http://kcpoi.baihongyu.com/