from typing import List

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # Calculate the total sum of all numbers in nums
        # This helps us define the range of possible sums (-total_sum to +total_sum)
        total_sum = sum(nums)

        # Initialize a memoization table with size:
        # rows -> number of elements in nums
        # cols -> range of possible sums from -total_sum to +total_sum
        # Using -inf as a marker for "not yet computed"
        memo = [[-float("inf")] * (2 * total_sum + 1) for _ in range(len(nums))]

        def dfs(index, current_sum):
            """
            Recursive DFS function to explore all combinations of '+' and '-'
            for each number to try and reach the target sum.

            Args:
                index: Current index in nums we are processing
                current_sum: The sum we have accumulated so far

            Returns:
                Number of ways to assign + or - to nums[index:] to reach the target
            """

            # Base case: If we've processed all numbers
            if index == len(nums):
                # If the accumulated sum equals the target, it's a valid way
                return 1 if current_sum == target else 0

            # If this state has been computed before, return it from memo
            if memo[index][current_sum + total_sum] != -float("inf"):
                return memo[index][current_sum + total_sum]

            # Choice 1: Add the current number
            add = dfs(index + 1, current_sum + nums[index])

            # Choice 2: Subtract the current number
            subtract = dfs(index + 1, current_sum - nums[index])

            # Store the total ways in memo to avoid recomputation
            memo[index][current_sum + total_sum] = add + subtract

            # Return the total ways for this state
            return add + subtract

        # Start DFS from index 0 and initial sum 0
        return dfs(0, 0)


from typing import List, Dict, Tuple

class Solution:
    def findTargetSumComb(self, nums: List[int], target: int) -> List[str]:
        """
        Return all +/− assignments that evaluate to `target`.
        Output format: strings like "+1-2+3" (one sign per number, in order).
        """
        memo: Dict[Tuple[int, int], List[List[str]]] = {}

        def dfs(index: int, current_sum: int) -> List[List[str]]:
            # If we've placed signs for all numbers, check if we hit target
            if index == len(nums):
                return [[]] if current_sum == target else []

            key = (index, current_sum)
            if key in memo:
                return memo[key]

            res: List[List[str]] = []

            # Option 1: place '+'
            for tail in dfs(index + 1, current_sum + nums[index]):
                res.append([f"+{nums[index]}"] + tail)

            # Option 2: place '−'
            for tail in dfs(index + 1, current_sum - nums[index]):
                res.append([f"-{nums[index]}"] + tail)

            memo[key] = res
            return res

        parts_lists = dfs(0, 0)
        # Join each list of parts into an expression string
        return ["".join(parts) for parts in parts_lists]

    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        """
        (Optional) Keep the original count API: just return the number of combinations.
        """
        return len(self.findTargetSumComb(nums, target))