【题目】

若干个数字间，使用加法或减法连接，最终得到目标和target，求所有满足条件解的个数

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

 

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 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
+1 + 1 + 1 + 1 - 1 = 3

Example 2:

Input: nums = [1], target = 1
Output: 1

 

【思路】

本体只有加法或减法，数字不可拆（比如120就是120，不能拆成1、20）

即每个数字都有加减两种可能，遍历所有情况即可

*关联题282 难

【代码】

 

class Solution {

    int count = 0;
    public int findTargetSumWays(int[] nums, int target) {
        calculate(nums, 0, 0, target);
        return count;
    }
    public void calculate(int[] nums, int i, int currsum, int target) {
        if (i == nums.length) {
            if (currsum == target)
                count++;
        } else {
            calculate(nums, i + 1, currsum + nums[i], target);
            calculate(nums, i + 1, currsum - nums[i], target);
        }
    }
}