K Sum

Question (LI.89)

Brute Force Code

Search problem at the first glance

def kSum(
    self, 
    arr: List[int], 
    size: int, 
    target_sum: int
) -> int:
    return self.countHelper(arr, 0, size, target_sum) 
    
def countHelper(
    self, 
    arr: List[int], 
    start: int, 
    size: int, 
    target_sum: int
) -> int:
        
        # print(f'{start}-{size}-{target_sum}')
        # print(f'current item {arr[start]}')
        count = 0
        
        # base 
        
        if size < 0: 
            return 0
        
        if size == 0:
            if target_sum > 0:
                # print("end of branch")
                return 0
            if target_sum == 0:
                # print("working solution")
                return 1        
        
        # recursion 
        
        if start < len(arr):
            
            for i in range(start, len(arr)):
            
                count += self.countHelper(
                    arr, i + 1, size - 1, target_sum - arr[i]
                )
            
        # return  
        
        return count

Memoized Code

Python has issues with initializing a multi-dimensional array

def kSum(self, arr: List[int], size: int, target_sum: int) -> int:
    
    memo = [
        [
            [
                None for k in range(target_sum + 1)
            ] for j in range(size + 1)
        ] for i in range(len(arr) + 1)
    ]
    
    
    # print(f'{memo}')
    
    return self.countHelper(memo, arr, 0, size, target_sum) 
    
def countHelper(
    self, 
    memo: List[List[List[int]]], 
    arr: List[int], 
    start: int, 
    size: int, 
    target_sum: int
) -> int:
        
        # print(f'{start}-{size}-{target_sum}')
        # print(f'current item {arr[start]}')
        count = 0
        
        # base 
        
        if size < 0 or target_sum < 0: 
            return 0
        
        if size == 0:
            if target_sum > 0:
                # print("end of branch")
                return 0
            if target_sum == 0:
                # print("working solution")
                return 1
            
        
        
        # recursion 
        
        if start < len(arr):
            
            if memo[start][size][target_sum] is not None:
                # print("memo worked")
                return memo[start][size][target_sum]
            
            for i in range(start, len(arr)):

                    count += self.countHelper(
                        memo, arr, i + 1, size - 1, target_sum - arr[i]
                    )
            memo[start][size][target_sum] = count 
            
        # return  
        return count 

Analysis

K Sum is a 0/1 knapsack because we want subsets. It has one more constraint. That's all.