494. Target Sum

LeetCode medium original: C# #array #backtracking #csharp #leetcode #medium #recursion #search

O texto da tarefa é traduzido do russo para o idioma selecionado. O código permanece sem alterações.

LeetCode Static

Вам дан array целых чисел nums и inteiro target.

Вы хотите создать выражение из nums, добавляя один из символов '+' или '-' перед каждым numberм в nums, а затем объединяя все числа.

НаExemplo, если nums = [2, 1], вы можете добавить '+' перед 2 и '-' перед 1, а затем объединить их, чтобы получить выражение "+2-1".

return количество различных выражений, которые можно построить и которые оцениваются в target.

Exemplo:

Input: nums = [1,1,1,1,1], target = 3

Output: 5

Explanation: There are 5 ways to assign symbols to make the sum of nums be 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 = 3

C# solução

correspondente/original

public class Solution {
    private int count = 0;
    public int FindTargetSumWays(int[] nums, int S) {
        Calculate(nums, 0, 0, S);
        return count;
    }
    private void Calculate(int[] nums, int i, int sum, int S) {
        if (i == nums.Length) {
            if (sum == S) {
                count++;
            }
        } else {
            Calculate(nums, i + 1, sum + nums[i], S);
            Calculate(nums, i + 1, sum - nums[i], S);
        }
    }
}

C++ solução

rascunho automático, revisar antes de enviar

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int count = 0;
    public int FindTargetSumWays(vector<int>& nums, int S) {
        Calculate(nums, 0, 0, S);
        return count;
    }
    private void Calculate(vector<int>& nums, int i, int sum, int S) {
        if (i == nums.size()) {
            if (sum == S) {
                count++;
            }
        } else {
            Calculate(nums, i + 1, sum + nums[i], S);
            Calculate(nums, i + 1, sum - nums[i], S);
        }
    }
}

Java solução

correspondente/original

public class Solution {
    int count = 0;
    
    public int findTargetSumWays(int[] nums, int S) {
        calculate(nums, 0, 0, S);
        return count;
    }
    
    public void calculate(int[] nums, int i, int sum, int S) {
        if (i == nums.length) {
            if (sum == S) {
                count++;
            }
        } else {
            calculate(nums, i + 1, sum + nums[i], S);
            calculate(nums, i + 1, sum - nums[i], S);
        }
    }
}

JavaScript solução

correspondente/original

class Solution {
    constructor() {
        this.count = 0;
    }

    findTargetSumWays(nums, S) {
        this.calculate(nums, 0, 0, S);
        return this.count;
    }

    calculate(nums, i, sum, S) {
        if (i === nums.length) {
            if (sum === S) {
                this.count++;
            }
        } else {
            this.calculate(nums, i + 1, sum + nums[i], S);
            this.calculate(nums, i + 1, sum - nums[i], S);
        }
    }
}

Python solução

correspondente/original

class Solution:
    def __init__(self):
        self.count = 0

    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        self.calculate(nums, 0, 0, S)
        return self.count

    def calculate(self, nums: List[int], i: int, sum: int, S: int):
        if i == len(nums):
            if sum == S:
                self.count += 1
        else:
            self.calculate(nums, i + 1, sum + nums[i], S)
            self.calculate(nums, i + 1, sum - nums[i], S)

Go solução

correspondente/original

type Solution struct {
    count int
}

func (s *Solution) findTargetSumWays(nums []int, S int) int {
    s.count = 0
    s.calculate(nums, 0, 0, S)
    return s.count
}

func (s *Solution) calculate(nums []int, i int, sum int, S int) {
    if i == len(nums) {
        if sum == S {
            s.count++
        }
    } else {
        s.calculate(nums, i+1, sum+nums[i], S)
        s.calculate(nums, i+1, sum-nums[i], S)
    }
}

Algorithm

Инициализация и вызов рекурсивной функции

Создайте переменную для хранения количества решений (count). Вызовите рекурсивную функцию calculate с начальными параметрами (nums, начальный индекс 0, начальная сумма 0, и target).

Рекурсивная функция calculate

Если текущий индекс равен длине arrayа, проверьте, равна ли текущая сумма значению target. Если да, увеличьте счетчик решений. В противном случае, вызовите функцию рекурсивно дважды: добавляя и вычитая текущее значение из суммы.

Возврат результата

После завершения всех рекурсивных вызовов return значение счетчика решений.

😎

Vacancies for this task

vagas ativas with overlapping task tags are mostradas.

Todas as vagas

Ainda não há vagas ativas.