题解 | #目标和#

import java.util.*;

/**
 * NC243 目标和
 * @author d3y1
 */
public class Solution {
    private int result = 0;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int findTargetSumWays (int[] nums, int target) {
        return solution1(nums, target);
        // return solution2(nums, target);
        // return solution3(nums, target);
    }

    /**
     * 动态规划
     *
     * sum表示所有整数的和
     * A表示所有前面加'+'号的整数和
     * B表示所有前面加'-'号的整数和
     * 依题意,可知:
     * A + B = sum
     * A + (-B) = target
     * => 2A = sum + target
     *
     * 转化为 求整数和为A的组合个数(方案数)
     *
     * dp[j]表示可累加为A的组合个数(方案数)
     *
     * dp[j] = dp[j] + dp[j-nums[i-1]]  , j >= nums[i-1]
     *
     * @param nums
     * @param target
     * @return
     */
    private int solution1(int[] nums, int target){
        int n = nums.length;
        if(n == 0){
            return 0;
        }

        int sum = 0;
        for(int i=0; i<n; i++){
            sum += nums[i];
        }

        // 2A = sum + target 奇数
        if((sum+target)%2 != 0){
            return 0;
        }

        int A = (sum + target) / 2;
        int[] dp = new int[A+1];
        dp[0] = 1;

        for(int i=1; i<=n; i++){
            // 每个整数只能选择一次 倒序遍历避免重复选取
            for(int j=A; j>=nums[i-1]; j--){
                dp[j] += dp[j-nums[i-1]];
            }
        }

        return dp[A];
    }

    /**
     * 动态规划
     *
     * sum表示所有整数的和
     * A表示所有前面加'+'号的整数和
     * B表示所有前面加'-'号的整数和
     * 依题意,可知:
     * A + B = sum
     * A + (-B) = target
     * => 2A = sum + target
     *
     * 转化为 求整数和为A的组合个数(方案数)
     *
     * dp[i][j]表示用nums前i个数可累加为A的组合个数(方案数)
     *
     *            { dp[i-1][j]                         , j < nums[i-1]
     * dp[i][j] = {
     *            { dp[i-1][j] + dp[i-1][j-nums[i-1]]  , j >= nums[i-1]
     *
     * @param nums
     * @param target
     * @return
     */
    private int solution2(int[] nums, int target){
        int n = nums.length;
        if(n == 0){
            return 0;
        }

        int sum = 0;
        for(int i=0; i<n; i++){
            sum += nums[i];
        }

        // 2A = sum + target 奇数
        if((sum+target)%2 != 0){
            return 0;
        }

        int A = (sum + target) / 2;
        int[][] dp = new int[n+1][A+1];
        dp[0][0] = 1;

        for(int i=1; i<=n; i++){
            for(int j=0; j<=A; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1]){
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }
            }
        }

        return dp[n][A];
    }

    /**
     * dfs
     * @param nums
     * @param target
     * @return
     */
    private int solution3(int[] nums, int target){
        if(nums.length == 0){
            return 0;
        }

        dfs(0, 0, nums, target);

        return result;
    }

    /**
     * 递归
     * @param level
     * @param sum
     * @param nums
     * @param target
     */
    private void dfs(int level, int sum, int[] nums, int target){
        if(level == nums.length){
            if(sum == target){
                result++;
            }
            return;
        }

        dfs(level+1, sum+nums[level], nums, target);
        dfs(level+1, sum-nums[level], nums, target);
    }
}