[Leetcode] 377. Combination Sum IV

Identifying the Problem

주어진 nums로 target을 만들 수 있는 가능한 경우의 수를 구한다.

Organizing thoughts

주어진 nums로 target 이전의 수를 만들 수 있는 경우를 다 구하고

target에서 각 nums를 뺏을 때 해당 경우의 수 값을 다 더해주면

target을 만드는 경우의 수가 된다. 

 

problem 은 target 의 가능한 경우의 수를 구하는 것이고,

sub-problem은 target 이전의 가능한 경우의 수를 미리 구해

target에 2,3,5를 뺏을 경우 각각의 가능한 경우의 수를 더함으로 답을 구한다.

 

Ex ) nums = [2,3,5]
target 12 라면

12에서 2,3,5를 뺀 10,9,5를 만들 수 있는 경우의 수
10-(2,3,5) 9 - (2,3,5) 5 - (2,3,5)... top-down 방식으로 생각했다면
1,2,3,4,5,6.... target의 값을 구해 bottom-up 방식으로 답을 구하면 된다.

Sourcecode

int combinationSum4(int* nums, int numsSize, int target)
{
    size_t combination_sum[1000] = {1, 0, 0};
    
    for (int i = 1; i <= target; i++) //target 이전까지의 count들을 미리 구하면됨
    {
        for (int j = 0; j < numsSize; j++)
        {
		if(0<=  i - nums[j])
            		combination_sum[i] +=  combination_sum[i - nums[j]]; 

		else 
			combination_sum[i] += 0; //index가 음수가 되는 경우 아무 것도 하지 않는다.
        }
    }
    
    return combination_sum[target];
}

New things learned

dynamic problem은

problem을 풀기 위해, sub-problem을 미리 풀어놓음으로, problem을 해결한다.

이 문제 같은 경우 dynamic problem의 중요한 부분은

예측 가능한 초기값을 설정해 두는 것인데,

주어진 nums로 0을 만드는 경우의 수는 1로 설정했다. 

(아무것도 안 더하는 게 하나의 경우의 수로 본다.)