Leetcode 494 Target Sum

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.

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

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

• Soruda bize bir sayı listesi ve bu sayıların pozitif ve negatif değerlerinin farklı kombinasyonları ile bulunması istenen target değeri veriliyor.
• Bu sorunun birden fazla çözüm yöntemi var.
• Backtracking ile çözmek istersek yapmamız gereken bir helper fonksiyonu oluşturmak ve bu fonksiyonu pozitif ve negatif sayıları çağıracak şekilde tekrar tekrar çağırmak.
• Örneğin [1,1,1,1,1] listesinden 3 elde edilmek isteniyor.
• Birinci değer [+1] yada [-1] alabilir.Bunu ağaçtaki ilk adım olarak düşünebiliriz. Daha sonra bir alt dala inersek [+1,+1],[+1,-1],[-1,+1],[-1,-1] elde ederiz.
• Bu şekilde ağacın 32 farklı kombinasyonlu sonucu bulunur.Bunlar arasında toplamı 3 ‘e eşit olanları da kontrol ederek bulabiliriz.

    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        def helper(index, acc):
            if index == len(nums):
                if acc == S:
                    return 1
                else:
                    return 0
            return helper(index + 1, acc + nums[index]) + helper(index + 1, acc - nums[index])
        return helper(0, 0)