01背包

import java.util.Arrays;

class Solution {
    public int findTargetSumWays(int[] nums, int target) {

        int sum = Arrays.stream(nums).sum();

        /**
         * 可以将数组分成两部分，一部分为正定义为left，一部分符号会改变定义为right
         * 故left + right == sum且left - right == target，得left = (sum + target) / 2
         * 题意转为，组成和为left的数字组合有多少种
         * 边界条件：如果target的绝对值大于总和，或者left为奇数，则不能达成题意
         */
        if (Math.abs(target) > sum || (sum + target) % 2 != 0){
            return 0;
        }

        int left = (sum + target) / 2;

        /**
         * 循环需left为正
         */
        if (left < 0){
            left = -left;
        }

        /**
         * 定义dp[j]为背包容量为j时，有多少种组合的数字可以填满
         * 初始化dp[0] == 1
         */
        int[] dp = new int[left + 1];
        dp[0] = 1;

        for (int i = 1; i <= nums.length; i++) {

            for (int j = left; j >= nums[i - 1]; j--) {
                dp[j] += dp[j - nums[i - 1]];
            }
        }

        return dp[left];
    }
}

/**
 * 时间复杂度 O(n^2)
 * 空间复杂度 O(n)
 */

https://leetcode-cn.com/problems/target-sum/