LeetCode目标和——回溯法与动态规划解决

494. 目标和

题目描述

给定一组非负整数序列，记为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。

解题思路分析

回溯法

    static int result = 0;
    /** * 回溯法
     */
    static int findTargetSumWays_1(int[] nums, int target){
        if (nums.length == 0)
            return 0;
        backtrack(nums,0,target);
        return result;