Количество способов вычисления целевого числа с использованием только элементов массива

Опубликовано: 20 Января, 2022

Для целочисленного массива найдите количество способов вычисления целевого числа, используя только элементы массива и оператор сложения или вычитания.

Пример:

Ввод: arr [] = {-3, 1, 3, 5}, k = 6
Выход: 4
Объяснение - 
- (-3) + (3)
+ (1) + (5)
+ (-3) + (1) + (3) + (5)
- (-3) + (1) - (3) + (5)

Ввод: arr [] = {2, 3, -4, 4}, k = 5
Выход: 6
Объяснение - 
+ (2) + (3)
+ (2) + (3) + (4) + (-4)
+ (2) + (3) - (4) - (-4)
- (3) + (4) - (-4)
- (2) + (3) + (4)
- (2) + (3) - (-4)

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Проблема аналогична задаче о рюкзаке 0-1, где для каждого предмета мы либо выбираем весь предмет, либо не выбираем его вообще (свойство 0-1). Идея здесь та же, т.е. мы либо включаем текущую цифру, либо игнорируем ее. Если мы включаем текущую цифру, мы вычитаем или добавляем ее из оставшейся цели и рекурсивно ищем оставшиеся цифры с новой целью. Если цель достигает 0, мы увеличиваем счет. Если мы обработали все элементы массива и цель не достигнута, счетчик остается неизменным.

Below is recursive implementation of above idea.

C++

// 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

// 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

Python3

# 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#

// 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

Выход :

Время Сложность вышеуказанного решения - O (3 ^ n), т.е. экспоненциальная.

Эта статья предоставлена Адитьей Гоэлем . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью и отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы

Количество способов вычисления целевого числа с использованием только элементов массива

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C++

Java

Python3

C#

РЕКОМЕНДУЕМЫЕ СТАТЬИ