LeetCode LCR 102. 目标和

Categories:

题目描述
思路分析
1. 解法一：数学转化 + 0-1 背包计数（推荐）
2. 解法二：DFS 回溯
相似题目

题目描述

✅ LCR 102. 目标和

思路分析

解法一：数学转化 + 0-1 背包计数（推荐）

核心思路：

设添加 + 号的数字集合为 P，添加 - 号的数字集合为 N，则 sum(P) + sum(N) = sum，sum(P) - sum(N) = target。

两式相加得 sum(P) = (sum + target) / 2，问题转化为：从数组中选若干数字，使其和恰好等于 bagSize = (sum + target) / 2，求方案数。

前置判断：若 (sum + target) 为奇数或 |target| > sum，则无解，返回 0。

定义 dp[j] 表示凑出和为 j 的方案数，初始值 dp[0] = 1。

状态转移（0-1 背包逆序遍历，防止同一元素被重复使用）：dp[j] += dp[j - num]。

复杂度分析：

时间复杂度：O(n × bagSize)，其中 n 为数组长度，bagSize = (sum + target) / 2。

空间复杂度：O(bagSize)，滚动数组只需一维 dp 表。

class Solution {
  public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int num : nums) {
      sum += num;
    }
    // 无解条件：奇偶性不符或目标超出范围
    if ((sum + target) % 2 != 0 || Math.abs(target) > sum) {
      return 0;
    }
    int bagSize = (sum + target) / 2;
    // dp[j] 表示凑出和为 j 的方案数
    int[] dp = new int[bagSize + 1];
    // 空集合凑出 0 的方案数为 1
    dp[0] = 1;
    for (int num : nums) {
      // 逆序遍历，保证每个元素只使用一次（0-1 背包）
      for (int j = bagSize; j >= num; j--) {
        dp[j] += dp[j - num];
      }
    }
    return dp[bagSize];
  }
}

func findTargetSumWays(nums []int, target int) int {
	sum := 0
	for _, num := range nums {
		sum += num
	}
	// 无解条件：奇偶性不符或目标超出范围
	if (sum+target)%2 != 0 || abs494(target) > sum {
		return 0
	}
	bagSize := (sum + target) / 2
	// dp[j] 表示凑出和为 j 的方案数
	dp := make([]int, bagSize+1)
	// 空集合凑出 0 的方案数为 1
	dp[0] = 1
	for _, num := range nums {
		// 逆序遍历，保证每个元素只使用一次（0-1 背包）
		for j := bagSize; j >= num; j-- {
			dp[j] += dp[j-num]
		}
	}
	return dp[bagSize]
}

func abs494(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

解法二：DFS 回溯

核心思路：

对数组中每个数字，递归地选择添加 + 或 -，累计当前和，到达末尾时判断是否等于 target。

时间复杂度较高，仅作为理解题意的辅助解法，不推荐在面试中作为主解。

复杂度分析：

时间复杂度：O(2ⁿ)，其中 n 为数组长度，每个元素有两种符号选择。

空间复杂度：O(n)，递归调用栈深度为 n。

class Solution {
  private int result = 0;

  public int findTargetSumWays(int[] nums, int target) {
    dfs(nums, target, 0, 0);
    return result;
  }

  private void dfs(int[] nums, int target, int index, int current) {
    // 所有数字已处理，判断当前和是否等于目标值
    if (index == nums.length) {
      if (current == target) {
        result++;
      }
      return;
    }
    // 选择添加 + 号
    dfs(nums, target, index + 1, current + nums[index]);
    // 选择添加 - 号
    dfs(nums, target, index + 1, current - nums[index]);
  }
}

func findTargetSumWays(nums []int, target int) int {
	result := 0
	var dfs func(index, current int)
	dfs = func(index, current int) {
		// 所有数字已处理，判断当前和是否等于目标值
		if index == len(nums) {
			if current == target {
				result++
			}
			return
		}
		// 选择添加 + 号
		dfs(index+1, current+nums[index])
		// 选择添加 - 号
		dfs(index+1, current-nums[index])
	}
	dfs(0, 0)
	return result
}

相似题目

题目	难度	考察点
416. 分割等和子集	中等	0-1 背包可行性
474. 一和零	中等	二维 0-1 背包
1049. 最后一块石头的重量 II	中等	0-1 背包（等价分割问题）
518. 零钱兑换 II	中等	完全背包计数（方案数）
377. 组合总和 Ⅳ	中等	完全背包有序计数
322. 零钱兑换	中等	完全背包最优值
279. 完全平方数	中等	完全背包最优值

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/71463337