Número de formas de calcular un número objetivo usando solo elementos de array

Dada una array de enteros, encuentre varias formas de calcular un número objetivo usando solo elementos de la array y un operador de suma o resta.

Ejemplo: 

Input: arr[] = {-3, 1, 3, 5}, k = 6
Output: 4
Explanation - 
- (-3) + (3)
+ (1) + (5)
+ (-3) + (1) + (3) + (5)
- (-3) + (1) - (3) + (5)

Input: arr[] = {2, 3, -4, 4}, k = 5
Output: 6
Explanation - 
+ (2) + (3)
+ (2) + (3) + (4) + (-4)
+ (2) + (3) - (4) - (-4)
- (3) + (4) - (-4)
- (2) + (3) + (4)
- (2) + (3) - (-4)

El problema es similar al Problema de la mochila 0-1 , donde para cada artículo, o seleccionamos el artículo completo o no lo seleccionamos en absoluto (propiedad 0-1). La idea sigue siendo la misma aquí, es decir, incluimos el dígito actual o lo ignoramos. Si incluimos el dígito actual, lo restamos o sumamos del objetivo restante y recursimos para los dígitos restantes con el nuevo objetivo. Si el objetivo llega a 0, incrementamos el conteo. Si hemos procesado todos los elementos de la array y no se alcanza el objetivo, el recuento permanece sin cambios.

A continuación se muestra la implementación recursiva de la idea anterior.  

// C++ program to find the number of ways to calculate
// a target number using only array elements and
// addition or subtraction operator.
#include <iostream>
#include <vector>
using namespace std;
 
// Function to find the number of ways to calculate
// a target number using only array elements and
// addition or subtraction operator.
int findTotalWays(vector<int> arr, int i, int k)
{
 
    // If target is reached, return 1
    if (k == 0 && 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 three cases
    // 1. Don't consider current element
    // 2. Consider current element and subtract it from target
    // 3. Consider current element and add it to target
    return findTotalWays(arr, i + 1, k)
           + findTotalWays(arr, i + 1, k - arr[i])
           + findTotalWays(arr, i + 1, k + arr[i]);
}
 
// Driver Program
int main()
{
    vector<int> arr = { -3, 1, 3, 5, 7 };
 
    // target number
    int k = 6;
 
    cout << findTotalWays(arr, 0, k) << endl;
 
    return 0;
}

// Java program to find the number
// of ways to calculate a target
// number using only array elements and
// addition or subtraction operator.
import java.util.*;
 
class GFG {
 
    // Function to find the number of ways to calculate
    // a target number using only array elements and
    // addition or subtraction operator.
    static int findTotalWays(Vector<Integer> arr, int i, int k)
    {
 
        // If target is reached, return 1
        if (k == 0 && 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 three cases
        // 1. Don't consider current element
        // 2. Consider current element and subtract it from target
        // 3. Consider current element and add it to target
        return findTotalWays(arr, i + 1, k)
            + findTotalWays(arr, i + 1, k - arr.get(i))
            + findTotalWays(arr, i + 1, k + arr.get(i));
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { -3, 1, 3, 5 };
        Vector<Integer> v = new Vector<Integer>();
        for (int a : arr) {
            v.add(a);
        }
 
        // target number
        int k = 6;
 
        System.out.println(findTotalWays(v, 0, k));
    }
}
 
// This code contributed by Rajput-Ji

# Python 3 program to find the number of
# ways to calculate a target number using
# only array elements and addition or
# subtraction operator.
 
# Function to find the number of ways to
# calculate a target number using only
# array elements and addition or
# subtraction operator.
def findTotalWays(arr, i, k):
 
    # If target is reached, return 1
    if (k == 0 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 three cases
    # 1. Don't consider current element
    # 2. Consider current element and
    # subtract it from target
    # 3. Consider current element and
    # add it to target
    return (findTotalWays(arr, i + 1, k) +
            findTotalWays(arr, i + 1, k - arr[i]) +
            findTotalWays(arr, i + 1, k + arr[i]))
 
# Driver Code
if __name__ == '__main__':
    arr = [-3, 1, 3, 5, 7]
 
    # target number
    k = 6
 
    print(findTotalWays(arr, 0, k))
     
# This code is contributed by
# Surendra_Gangwar

// C# program to find the number
// of ways to calculate a target
// number using only array elements and
// addition or subtraction operator.
using System;
using System.Collections.Generic;
 
class GFG {
 
    // Function to find the number of ways to calculate
    // a target number using only array elements and
    // addition or subtraction operator.
    static int findTotalWays(List<int> arr, int i, int k)
    {
        // If target is reached, return 1
        if (k == 0 && i ==  arr.Count) {
            return 1;
        }
 
        // If all elements are processed and
        // target is not reached, return 0
        if (i >= arr.Count) {
            return 0;
        }
 
        // Return total count of three cases
        // 1. Don't consider current element
        // 2. Consider current element and subtract it from target
        // 3. Consider current element and add it to target
        return findTotalWays(arr, i + 1, k)
            + findTotalWays(arr, i + 1, k - arr[i])
            + findTotalWays(arr, i + 1, k + arr[i]);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[] arr = { -3, 1, 3, 5, 7 };
        List<int> v = new List<int>();
        foreach(int a in arr)
        {
            v.Add(a);
        }
 
        // target number
        int k = 6;
 
        Console.WriteLine(findTotalWays(v, 0, k));
    }
}
 
// This code has been contributed by 29AjayKumar

<script>
 
// Javascript program to find the number
// of ways to calculate a target
// number using only array elements and
// addition or subtraction operator.
 
// Function to find the number of ways to
// calculate a target number using only
// array elements and addition or
// subtraction operator.
function findTotalWays(arr, i, k)
{
     
    // If target is reached, return 1
    if (k == 0 && 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 three cases
    // 1. Don't consider current element
    // 2. Consider current element and
    //    subtract it from target
    // 3. Consider current element and
    //    add it to target
    return findTotalWays(arr, i + 1, k) +
           findTotalWays(arr, i + 1, k - arr[i]) +
           findTotalWays(arr, i + 1, k + arr[i]);
}
 
// Driver code
let arr = [ -3, 1, 3, 5 ,7 ];
let k = 6;
 
document.write(findTotalWays(arr, 0, k));
 
// This code is contributed by rag2127
 
</script>

Producción : 

10

Complejidad de tiempo: O(3^n)
Espacio auxiliar: O(n) 

Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.