[21/10/04 KATA NINJA] Target Sum

코드

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function(nums, target) {
    let count = 0;
    
    DFS(0,0);
    
    return count;    
    
    function DFS(current,level){     
        
        
        if(level === nums.length - 1){
            if(target === current+nums[level]) count++;
            
            if(target === current-nums[level]) count++;
            
            
        }else{
            if(validation(current+nums[level],level+1)) DFS(current+nums[level],level+1);
                
            if(validation(current-nums[level],level+1)) DFS(current-nums[level],level+1);
        }
                
    
        
            
        
        
    }
    function validation(next,start){
        const sub = nums.slice(start).reduce((a,b)=>a+b)
        
        return next-sub <= target && target <= next+sub 
        
        
        
    }
};

위 코드는 성능이 조금 구리다..

23% 성능.

메모이제이션을 사용하여 개선해보자.

개선 코드

var findTargetSumWays = function(n, t) {
    const memo = {};
    
    return DFS(t);
    
    function DFS(target, level = 0) {
        
        const hash = `${level},${target}`
        
        if(memo[hash]){
            
            return memo[hash]
            
        }
        
        if(level === n.length - 1){
            // 레벨이 마지막 인덱스라면 
            
            // 1. 마지막 인덱스 값이 0이면서 현재 값이 0이라면 -> 2번 늘려준다 (+,-) 해도 같으므로
            
            // 2. 마지막 인덱스 값이 0이 아니면서 다음 값과 현재 타겟 값을 절대 비교해주었을 때 같으면 -> 1회
            
            // 3. 아니라면 0을 리턴

            if(n[level] === 0 && target === 0 ) return 2;
            
            if(n[level] === target || n[level] === -target) return 1;
            
            return 0;
            
        }
        
            
        const res = DFS(target - n[level],level+1) + DFS(target+n[level],level+1)
        
        memo[hash] = res;
        
        
        return res;
        
       
        

    }
};

메모이제이션을 추가해주었으나 더 느리다...?

아래 코드를 주석으로 변경해주어야

if(memo[hash]){
            
            return memo[hash]
            
        }

//if(memo[hash] !== undefined) return memo[hash] 로 바꾸어줘야함.

다음의 실행속도를 볼 수 있다. (why?)

dp로 풀면 더 빠르다.

다시 풀어보자.

var findTargetSumWays = function(nums, target) {
    let total = nums.reduce((a,b)=>a+b);
    
    const dp = [...new Array(nums.length+1)].map(()=>[...new Array(total*2+1)].map(()=>0));
    

    // meaning : row -> 몇 개의 요소가 관여하였는가. column -> total을 기준으로 큰 index는 양수 작은 index는 음수이다. (관여된 요소의)총합을 의미한다.
    
    if(total < Math.abs(target)){
        // 다 더하거나 다 뺄때보다 오히려 타겟이 크면 찾을 수 없다.
        return 0;
    }
    
    if(nums.length === 1 && Math.abs(total) === Math.abs(target)){
        return 1;
    }
    
    if(nums.length === 1 && Math.abs(total) !== Math.abs(target)){
        return 0;
    }
    
    
    dp[0][total] = 1; // what?
    
    for(let r=0;r<nums.length;r++){
        // dp 배열의 nums.length 로우에 값이 채워져있다. 종료되면
        for(let c=0;c<dp[r].length;c++){
            if(dp[r][c] !== 0){
              // dp[r+1][c+nums[r]]가 몇개 나올수있는가
              // dp[r][c]를 더 해준다.
              
              // 이전까지 몇개가 나왔는지 더해준다.
                dp[r+1][c+nums[r]] += dp[r][c];
                dp[r+1][c-nums[r]] += dp[r][c];
            }
            
        }
    }
    
    

    return dp[nums.length][total + target];

};