[PYTHON] Let Code Day 39 "494. Target Sum" starting from scratch

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 38 starting from zero "208. Implement Trie (Prefix Tree)"

I'm currently solving the Top 100 Liked Questions Medium. I solved all Easy, so if you are interested, please go to the table of contents.

Twitter I'm doing it.

problem

494. Target Sum

Given an array of natural numbers nums and a natural number S. Given + and-, add or subtract all the arrays and return the number of combinations that match the value of S.

Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation:

-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

There are 5 ways to assign symbols to make the sum of nums be target 3.

It is like this. You can see what I want to say from the example.

solution

class Solution:
    def calc(self,nums,index,sums,S):
        if index == len(nums):
            if sums == S:
                self.count += 1
        else:
            self.calc(nums,index+1,sums+nums[index],S)
            self.calc(nums,index+1,sums-nums[index],S)
            
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        self.count = 0
        self.calc(nums,0,0,S)
        return self.count
# Time Limit Exceeded

At first I wrote it with the intention of solving it with Bruteforce, but the time has expired.

So I rewrote it.

from functools import lru_cache

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        
        @lru_cache(None)
        def calc(index,S):
            if index == 0:
                 return  int(nums[0] == S) + int(-nums[0] == S)
            return  calc(index-1, S - nums[index]) + calc(index-1, S + nums[index])
    
        return calc(len(nums)-1, S)
# Runtime: 240 ms, faster than 74.28% of Python3 online submissions for Target Sum.
# Memory Usage: 31.5 MB, less than 50.00% of Python3 online submissions for Target Sum.

Leet Code Day 25 "70. Climbing Stairs" starting from zero However, using the @lru_cache that appeared, I prepared and implemented calc as a helper function.

I was able to implement it with a good feeling, so it is important to continue learning and leave it in shape.

This time around here. Thank you for your support.