Combination Sum IV

유의할점

다이나믹 프로그래밍이 언제 필요한가

풀이

remain에 해당하는 수를 메모한다.

remain에 메모되는 수는 remain - nums[i]의 경우의수의 합이다.

음수가 포함될 경우 -1로 초기화하면 안된다. → 최소값 or 최대값

음수가 포함될 경우 remain이 0일때 backtracking 하면 안된다.

코드

C++

class Solution {
private:
    int memo[1001];
public:
    int makeCombi(vector<int>& nums, int remain){
        if(remain < 0)// if negative numbers are allowed , it should be removed
            return 0;
        if(remain == 0)
            return 1;

        if(memo[remain]!=-1)
            return memo[remain];
        
        int &res = memo[remain];
        res = 0;
        
        for(int i = 0; i < nums.size(); i++){
            res += makeCombi(nums, remain-nums[i]);
        }
        
        return res;
    }
    
    int combinationSum4(vector<int>& nums, int target) {
        memset(memo,-1,sizeof(memo)); // if negative numbers are allowed , it should not be-1 but be changed 
        return makeCombi(nums, target); 
    }
};