目标和

题目

题目地址：https://leetcode-cn.com/problems/target-sum/

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

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

示例 1:

输入: 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。

答案

使用递归实现

package com.jarome.leetcode.test1;

public class SolutionSumWays {

    public int findTargetSumWays(int[] nums, int S) {
        return count(nums, S, 0, 0);
    }

    private int count(int[] nums, int S, int base, int index) {
        if (index == nums.length) {
            if (base == S) {
                return 1;
            }
            return 0;
        }
        // 两种处理，一个加 一个减
        int newIndex = index + 1;
        int count = 0;
        count = count + count(nums, S, base - nums[index], newIndex);
        count = count + count(nums, S, base + nums[index], newIndex);
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        SolutionSumWays s = new SolutionSumWays();
        int targetSumWays = s.findTargetSumWays(nums, 3);
        System.out.println(targetSumWays);
    }
}