Target sum

Array Dynamic Programming Backtracking

51.9% acceptance

Jan 13, 2026

12329

414

You are given an integer array nums and an integer target. You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers. For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1". Return the number of different expressions that you can build, which evaluates to target.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
    let mut memo = HashMap::new();
    Self::dfs(&nums, 0, 0, target, &mut memo)
  }
  
  fn dfs(nums: &[i32], idx: usize, sum: i32, target: i32, memo: &mut HashMap<(usize, i32), i32>) -> i32 {
    if idx == nums.len() {
      return if sum == target { 1 } else { 0 };
    }
    
    if let Some(&result) = memo.get(&(idx, sum)) {
      return result;
    }
    
    let add = Self::dfs(nums, idx + 1, sum + nums[idx], target, memo);
    let sub = Self::dfs(nums, idx + 1, sum - nums[idx], target, memo);
    let result = add + sub;
    
    memo.insert((idx, sum), result);
    result
  }
}