Target Sum

https://leetcode.com/problems/target-sum/

주어진 값 S가 되도록 제시된 정수 집합으로 조합을 찾는 문제. 부호가 +,-가 될 수 있다. 어차피 모든 조합을 검사해야 하므로, 동적 프로그래밍 기법을 써서 반복 계산을 피해야 한다.

import collections


class Solution:
    def findTargetSumWays( self, nums, S: int ) -> int:
        if not nums:
            return 0

        # key: remain nums, value: sum cases
        caches = collections.defaultdict( lambda : collections.defaultdict( int ) )
        count, _ = self.__findTargetSumWays( nums, S, caches )

        return count


    def __findTargetSumWays( self, nums, S, caches ):
        if not nums:
            if S:
                return 0, {}
            else:
                return 1, {}
        else:
            key = tuple( nums )
            count = 0

            if key in caches:
                _caches = caches[ key ]

                for cache, _count in _caches.items():
                    if cache == S:
                        count += _count

                return count, _caches
            else:
                num = nums[ 0 ]
                remainNums = nums[ 1 : ]
                tempCaches = collections.defaultdict( int )

                for num in ( num, -num ):
                    _count, _caches = self.__findTargetSumWays( remainNums, S - num, caches )
                    count += _count

                    if not _caches:
                        tempCaches[ num ] += 1
                    else:
                        for cache, _count in _caches.items():
                            tempCaches[ num + cache ] += _count

                for num, _count in tempCaches.items():
                    caches[ key ][ num ] += _count

                return count, tempCaches