Given an array arr[] and an integer target. We want to build an expression out of arr[] by adding one of the symbols '+' and '-' before each integer in arr[] and then concatenate all the integers. Determine the number of different expressions that can be built, which evaluates to target.
Example:
Input : arr[] = [1, 1, 1, 1, 1], target = 3
Output: 5
Explanation: There are 5 ways for target 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
+1 + 1 + 1 + 1 - 1 = 3Input: arr[] = [1], target = 1
Output: 1Input : arr[] = [1, 2, 2, 1], target = 2
Output: 2
Explanation: There are 2 ways for 2
1 - 2 + 2 + 1
1 + 2 - 2 + 1
Try it on GfG Practice
[Naive Approach] Using Recursion - O(2^n) Time and O(n) Auxiliary Space
The idea is to explore all possible expressions by assigning either a
'+'or'-'sign to each element of the array.
- For every element, there are two choices: add it to the current sum or subtract it from the current sum.
- At each step, the current index and the cumulative sum together define the state of the recursion.
- When all elements have been processed, the current sum is compared with the target. If they are equal, one valid expression is found; otherwise, it is discarded.
#include <iostream>
#include <vector>
using namespace std;
int findPossibleWays(vector<int>& arr, int i, int s, int& target)
{
// If target is reached, return 1
if (s == target && i == arr.size())
return 1;
// If all elements are processed and
// target is not reached, return 0
if (i >= arr.size())
return 0;
// Return total count of two cases
// 1. Add current element
// 2. Subtract current element
return findPossibleWays(arr, i + 1, s + arr[i], target)
+ findPossibleWays(arr, i + 1, s - arr[i], target);
}
int findTotalWays(vector<int>& arr , int target){
return findPossibleWays(arr , 0 , 0 , target);
}
int main()
{
vector<int> arr = { 1, 1, 1, 1, 1 };
int target = 3;
cout << findTotalWays(arr , target) << endl;
return 0;
}
public class GFG {
static int findPossibleWays(int[] arr, int i, int s, int target) {
// If target is reached, return 1
if (s == target && i == arr.length)
return 1;
// If all elements are processed and
// target is not reached, return 0
if (i >= arr.length)
return 0;
// Return total count of two cases
// 1. Add current element
// 2. Subtract current element
return findPossibleWays(arr, i + 1, s + arr[i], target)
+ findPossibleWays(arr, i + 1, s - arr[i], target);
}
static int findTotalWays(int[] arr, int target) {
return findPossibleWays(arr, 0, 0, target);
}
public static void main(String[] args) {
int[] arr = {1, 1, 1, 1, 1};
int target = 3;
System.out.println(findTotalWays(arr, target));
}
}
# Function to find the number of ways to calculate
def findPossibleWays(arr, i, s, target):
# If target is reached, return 1
if s == target and i == len(arr):
return 1
# If all elements are processed and
# target is not reached, return 0
if i >= len(arr):
return 0
# Return total count of two cases
# 1. Add current element
# 2. Subtract current element
return (findPossibleWays(arr, i + 1, s + arr[i], target) +
findPossibleWays(arr, i + 1, s - arr[i], target))
def findTotalWays(arr, target):
return findPossibleWays(arr, 0, 0, target)
if __name__ == "__main__":
arr = [1, 1, 1, 1, 1]
target = 3
print(findTotalWays(arr, target))
using System;
class GFG
{
static int FindTotalWays(int[] arr, int i, int s, int target)
{
// If target is reached, return 1
if (s == target && i == arr.Length)
return 1;
// If all elements are processed and
// target is not reached, return 0
if (i >= arr.Length)
return 0;
// Return total count of two cases
// 1. Add current element
// 2. Subtract current element
return FindTotalWays(arr, i + 1, s + arr[i], target)
+ FindTotalWays(arr, i + 1, s - arr[i], target);
}
static void Main()
{
int[] arr = { 1, 1, 1, 1, 1 };
int target = 3;
Console.WriteLine(FindTotalWays(arr, 0, 0, target));
}
}
function findPossibleWays(arr, i, s, target) {
// If target is reached, return 1
if (s === target && i === arr.length)
return 1;
// If all elements are processed and
// target is not reached, return 0
if (i >= arr.length)
return 0;
// Return total count of two cases
// 1. Add current element
// 2. Subtract current element
return findPossibleWays(arr, i + 1, s + arr[i], target)
+ findPossibleWays(arr, i + 1, s - arr[i], target);
}
function findTotalWays(arr, target) {
return findPossibleWays(arr, 0, 0, target);
}
// driver code
let arr = [1, 1, 1, 1, 1];
let target = 3;
console.log(findTotalWays(arr, target));
Output
5
[Better Approach-1] Using Top Down DP (Memoization) - O(n*Sum) and O(n*Sum) Space
This approach optimizes the recursive solution by storing results of overlapping subproblems. Here, dp[i][s] stores the number of ways to achieve a cumulative sum s using elements from index i onward. Since the cumulative sum can become negative, an offset equal to the total sum of all elements is used to map sums to valid indices.
#include <iostream>
#include <vector>
using namespace std;
int findPossibleWays(vector<int>& arr, vector<vector<int> >& dp,
int i, int s, int &target, int &total_sum)
{
// If target is reached, return 1
if (s == target && i == arr.size())
return 1;
// If all elements are processed and
// target is not reached, return 0
if (i >= arr.size())
return 0;
// s + total_sum to avoid negative values
if (dp[i][s + total_sum] != -1)
return dp[i][s + total_sum];
// Return total count of two cases
// 1. Add current element
// 2. Subtract current element
return dp[i][s + total_sum]
= findPossibleWays(arr, dp, i + 1, s + arr[i],
target, total_sum)
+ findPossibleWays(arr, dp, i + 1, s - arr[i],
target, total_sum);
}
int findTotalWays(vector<int>& arr , int target){
int n = arr.size();
int totalSum = 0;
for(int i = 0; i < n; i++){
totalSum += arr[i];
}
vector<vector<int>> dp(n , vector<int>(2*totalSum + 1, -1));
return findPossibleWays(arr , dp , 0 , 0 , target , totalSum);
}
int main(){
vector<int> arr = {1 , 1 , 1 , 1 , 1};
int target = 3;
cout << findTotalWays(arr , target) << endl;
return 0;
}
import java.util.Arrays;
public class GFG {
static int findPossibleWays(int[] arr, int[][] dp,
int i, int s, int target, int total_sum) {
// If target is reached, return 1
if (s == target && i == arr.length)
return 1;
// If all elements are processed and target is not reached, return 0
if (i >= arr.length)
return 0;
// s + total_sum to avoid negative values
if (dp[i][s + total_sum] != -1)
return dp[i][s + total_sum];
// Return total count of two cases
// 1. Add current element
// 2. Subtract current element
dp[i][s + total_sum] =
findPossibleWays(arr, dp, i + 1, s + arr[i], target, total_sum)
+ findPossibleWays(arr, dp, i + 1, s - arr[i], target, total_sum);
return dp[i][s + total_sum];
}
static int findTotalWays(int[] arr, int target) {
int n = arr.length;
int totalSum = 0;
for (int x : arr)
totalSum += x;
int[][] dp = new int[n][2 * totalSum + 1];
// Fill dp with -1
for (int i = 0; i < n; i++)
Arrays.fill(dp[i], -1);
return findPossibleWays(arr, dp, 0, 0, target, totalSum);
}
public static void main(String[] args) {
int[] arr = {1, 1, 1, 1, 1};
int target = 3;
System.out.println(findTotalWays(arr, target));
}
}
def findPossibleWays(arr, dp, i, s, target, totalSum):
# If target is reached, return 1
if s == target and i == len(arr):
return 1
# If all elements are processed and
# target is not reached, return 0
if i >= len(arr):
return 0
# s + total_sum to avoid negative values
if dp[i][s + totalSum] != -1:
return dp[i][s + totalSum]
# Return total count of two cases
# 1. Add current element
# 2. Subtract current element
dp[i][s + totalSum] = (
findPossibleWays(arr, dp, i + 1, s + arr[i], target, totalSum)
+ findPossibleWays(arr, dp, i + 1, s - arr[i], target, totalSum)
)
return dp[i][s + totalSum]
def findTotalWays(arr, target):
n = len(arr)
totalSum = sum(arr)
dp = [[-1] * (2 * totalSum + 1) for _ in range(n)]
return findPossibleWays(arr, dp, 0, 0, target, totalSum)
if __name__ == "__main__":
arr = [1, 1, 1, 1, 1]
target = 3
print(findTotalWays(arr, target))
using System;
using System.Collections.Generic;
class GFG
{
static int findPossibleWays(List<int> arr, int[,] dp,
int i, int s, int target, int totalSum)
{
// If target is reached, return 1
if (s == target && i == arr.Count)
return 1;
// If all elements are processed and
// target is not reached, return 0
if (i >= arr.Count)
return 0;
// s + total_sum to avoid negative values
if (dp[i, s + totalSum] != -1)
return dp[i, s + totalSum];
// Return total count of two cases
// 1. Add current element
// 2. Subtract current element
dp[i, s + totalSum] =
findPossibleWays(arr, dp, i + 1, s + arr[i], target, totalSum)
+ findPossibleWays(arr, dp, i + 1, s - arr[i], target, totalSum);
return dp[i, s + totalSum];
}
static int findTotalWays(List<int> arr, int target)
{
int totalSum = 0;
foreach (int x in arr)
totalSum += x;
int[,] dp = new int[arr.Count, 2 * totalSum + 1];
for (int i = 0; i < arr.Count; i++)
for (int j = 0; j < 2 * totalSum + 1; j++)
dp[i, j] = -1;
return findPossibleWays(arr, dp, 0, 0, target, totalSum);
}
static void Main()
{
List<int> arr = new List<int> { 1, 1, 1, 1, 1 };
int target = 3;
Console.WriteLine(findTotalWays(arr, target));
}
}
function findPossibleWays(arr, dp, i, s, target, totalSum) {
// If target is reached, return 1
if (s === target && i === arr.length)
return 1;
// If all elements are processed and
// target is not reached, return 0
if (i >= arr.length)
return 0;
// s + total_sum to avoid negative values
if (dp[i][s + totalSum] !== -1)
return dp[i][s + totalSum];
// Return total count of two cases
// 1. Add current element
// 2. Subtract current element
dp[i][s + totalSum] =
findPossibleWays(arr, dp, i + 1, s + arr[i], target, totalSum) +
findPossibleWays(arr, dp, i + 1, s - arr[i], target, totalSum);
return dp[i][s + totalSum];
}
function findTotalWays(arr, target) {
let totalSum = arr.reduce((a, b) => a + b, 0);
let dp = Array(arr.length)
.fill(0)
.map(() => Array(2 * totalSum + 1).fill(-1));
return findPossibleWays(arr, dp, 0, 0, target, totalSum);
}
// driver code
let arr = [1, 1, 1, 1, 1];
let target = 3;
console.log(findTotalWays(arr, target));
Output
5
[Better Approach-2] Using Bottom Up DP (Tabulation) - O(n*Sum) Time and O(n*Sum) Space
In this approach, a DP table is built iteratively. Here, dp[i][j] represents the number of ways to form a sum j using the first i elements of the array. The table is initialized to represent zero elements forming a sum of zero. For each element, the table is updated by propagating counts for both adding and subtracting the current value. Each state depends on results from the previous row, ensuring that all valid expressions are counted efficiently.
#include <iostream>
#include <vector>
using namespace std;
int findTotalWays(vector<int>& arr , int& target){
int n = arr.size();
int totalSum = 0;
for(int i = 0; i < n; i++){
totalSum += arr[i];
}
vector<vector<int>> dp(n + 1, vector<int> (2*totalSum + 1 , 0));
dp[0][totalSum] = 1;
for(int i = 1 ; i <= n ; i++){
for(int j = 0; j <= 2*totalSum; j++){
// add current element
if(j + arr[i-1] <= 2*totalSum)
dp[i][j + arr[i-1]] += dp[i - 1][j];
// subtract current element
if(j - arr[i-1] >= 0)
dp[i][j - arr[i-1]] += dp[i - 1][j];
}
}
return dp[n][target + totalSum];
}
int main() {
vector<int> arr = {1 , 1 , 1 , 1 , 1};
int target = 3;
cout << findTotalWays(arr , target) << endl;
return 0;
}
public class GFG {
static int findTotalWays(int[] arr, int target) {
int n = arr.length;
int totalSum = 0;
for (int x : arr) totalSum += x;
int[][] dp = new int[n + 1][2 * totalSum + 1];
dp[0][totalSum] = 1;
for (int i = 1; i <= n; i++) {
int val = arr[i - 1];
for (int j = 0; j <= 2 * totalSum; j++) {
// add current element
if (j + val <= 2 * totalSum)
dp[i][j + val] += dp[i - 1][j];
// subtract current element
if (j - val >= 0)
dp[i][j - val] += dp[i - 1][j];
}
}
return dp[n][target + totalSum];
}
public static void main(String[] args) {
int[] arr = {1, 1, 1, 1, 1};
int target = 3;
System.out.println(findTotalWays(arr, target));
}
}
def find_total_ways(arr, target):
n = len(arr)
totalSum = sum(arr)
dp = [[0] * (2 * totalSum + 1) for _ in range(n + 1)]
dp[0][totalSum] = 1
for i in range(1, n + 1):
val = arr[i - 1]
for j in range(2 * totalSum + 1):
if dp[i - 1][j] != 0:
# Add current element
if j + val <= 2 * totalSum:
dp[i][j + val] += dp[i - 1][j]
# Subtract current element
if j - val >= 0:
dp[i][j - val] += dp[i - 1][j]
return dp[n][target + totalSum]
if __name__ == "__main__":
arr = [1, 1, 1, 1, 1]
target = 3
print(find_total_ways(arr, target))
using System;
using System.Collections.Generic;
class GFG
{
static int findTotalWays(List<int> arr, int target)
{
int n = arr.Count;
int totalSum = 0;
foreach (int x in arr)
totalSum += x;
int[,] dp = new int[n + 1, 2 * totalSum + 1];
dp[0, totalSum] = 1;
for (int i = 1; i <= n; i++)
{
int val = arr[i - 1];
for (int j = 0; j <= 2 * totalSum; j++)
{
if (dp[i - 1, j] != 0)
{
// Add current element
if (j + val <= 2 * totalSum)
dp[i, j + val] += dp[i - 1, j];
// Subtract current element
if (j - val >= 0)
dp[i, j - val] += dp[i - 1, j];
}
}
}
return dp[n, target + totalSum];
}
static void Main()
{
List<int> arr = new List<int> { 1, 1, 1, 1, 1 };
int target = 3;
Console.WriteLine(findTotalWays(arr, target));
}
}
function findTotalWays(arr, target) {
const n = arr.length;
const totalSum = arr.reduce((a, b) => a + b, 0);
const dp = Array.from({ length: n + 1 }, () =>
Array(2 * totalSum + 1).fill(0)
);
dp[0][totalSum] = 1;
for (let i = 1; i <= n; i++) {
let val = arr[i - 1];
for (let j = 0; j <= 2 * totalSum; j++) {
if (dp[i - 1][j] !== 0) {
// Add current element
if (j + val <= 2 * totalSum)
dp[i][j + val] += dp[i - 1][j];
// Subtract current element
if (j - val >= 0)
dp[i][j - val] += dp[i - 1][j];
}
}
}
return dp[n][target + totalSum];
}
// driver code
let arr = [1, 1, 1, 1, 1];
let target = 3;
console.log(findTotalWays(arr, target));
Output
5
[Expected Approach] Using Space Optimization - O(n*Sum) Time and O(Sum) Space
This approach reduces space usage by observing that each DP row depends only on the previous row. Instead of maintaining a full 2D table, two 1D arrays are used to represent the previous and current states.
Here, each index in the array stores the number of ways to achieve the corresponding sum after processing a certain number of elements.
After computing one row, the current array replaces the previous one. This optimization preserves correctness while significantly reducing memory usage.
#include <iostream>
#include <vector>
using namespace std;
int findTotalWays(vector<int>& arr , int target){
int n = arr.size();
int totalSum = 0;
for(int i = 0; i < n; i++){
totalSum += arr[i];
}
// only two 1D arrays curr and prev
vector<int> prev(2*totalSum + 1 , 0);
vector<int> curr;
prev[totalSum] = 1;
for(int i = 1 ; i <= n ; i++){
curr.assign(2*totalSum + 1 , 0);
for(int sum = 0; sum <= 2*totalSum; sum++){
// add current element
if(sum + arr[i - 1] <= 2*totalSum)
curr[sum + arr[i - 1]] += prev[sum];
// subtract current element
if(sum - arr[i - 1] >= 0)
curr[sum - arr[i - 1]] += prev[sum];
}
prev = curr;
}
return prev[target + totalSum];
}
int main(){
vector<int> arr = {1 , 1 , 1 , 1 , 1};
int target = 3;
cout << findTotalWays(arr , target) << endl;
return 0;
}
import java.util.Arrays;
public class GFG {
static int findTotalWays(int[] arr, int target) {
int n = arr.length;
int totalSum = 0;
for (int x : arr)
totalSum += x;
int size = 2 * totalSum + 1;
// only two 1D arrays curr and prev
int[] prev = new int[size];
int[] curr = new int[size];
prev[totalSum] = 1;
for (int i = 1; i <= n; i++) {
Arrays.fill(curr, 0);
int val = arr[i - 1];
for (int sum = 0; sum < size; sum++) {
// add current element
if (sum + val < size)
curr[sum + val] += prev[sum];
// subtract current element
if (sum - val >= 0)
curr[sum - val] += prev[sum];
}
prev = curr.clone();
}
return prev[target + totalSum];
}
public static void main(String[] args) {
int[] arr = {1, 1, 1, 1, 1};
int target = 3;
System.out.println(findTotalWays(arr, target));
}
}
def find_total_ways(arr, target):
n = len(arr)
total_sum = sum(arr)
size = 2 * total_sum + 1
# only two 1D arrays curr and prev
prev = [0] * size
curr = [0] * size
prev[total_sum] = 1
for i in range(1, n + 1):
curr = [0] * size
val = arr[i - 1]
for s in range(size):
# add current element
if s + val < size:
curr[s + val] += prev[s]
# subtract current element
if s - val >= 0:
curr[s - val] += prev[s]
prev = curr[:]
return prev[target + total_sum]
if __name__ == "__main__":
arr = [1, 1, 1, 1, 1]
target = 3
print(find_total_ways(arr, target))
using System;
using System.Collections.Generic;
class GFG
{
static int findTotalWays(List<int> arr, int target)
{
int n = arr.Count;
int totalSum = 0;
foreach (int x in arr)
totalSum += x;
int size = 2 * totalSum + 1;
// only two 1D arrays curr and prev
int[] prev = new int[size];
int[] curr = new int[size];
prev[totalSum] = 1;
for (int i = 1; i <= n; i++)
{
Array.Clear(curr, 0, size);
int val = arr[i - 1];
for (int sum = 0; sum < size; sum++)
{
// add current element
if (sum + val < size)
curr[sum + val] += prev[sum];
// subtract current element
if (sum - val >= 0)
curr[sum - val] += prev[sum];
}
Array.Copy(curr, prev, size);
}
return prev[target + totalSum];
}
static void Main()
{
List<int> arr = new List<int> { 1, 1, 1, 1, 1 };
int target = 3;
Console.WriteLine(findTotalWays(arr, target));
}
}
function findTotalWays(arr, target) {
const n = arr.length;
const totalSum = arr.reduce((a, b) => a + b, 0);
const size = 2 * totalSum + 1;
// only two 1D arrays curr and prev
let prev = new Array(size).fill(0);
let curr = new Array(size).fill(0);
prev[totalSum] = 1;
for (let i = 1; i <= n; i++) {
curr.fill(0);
let val = arr[i - 1];
for (let s = 0; s < size; s++) {
// add current element
if (s + val < size)
curr[s + val] += prev[s];
// subtract current element
if (s - val >= 0)
curr[s - val] += prev[s];
}
prev = [...curr];
}
return prev[target + totalSum];
}
// driver code
let arr = [1, 1, 1, 1, 1];
let target = 3;
console.log(findTotalWays(arr, target));
Output
5