[LeetCode] 377. Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/description/

Combination Sum IV - LeetCode

문제 유형 : 조합 / 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

 

정수 배열 nums와 정수 target이 주어진다. 합하여 target를 만들 수 있는 숫자 조합을 만들어라. 숫자는 중복 사용가능하다.

정답은 32비트정수 이내로 나오게 만들어져있다.

 

풀이

dp테이블을 만들어서, dp[i]는 i를 만들기 위한 조합의 수로 한다.

재귀 함수를 만든다

1. 남은 숫자가 0이면, 조합을 하나 만든 것이므로 1을 반환시킨다.

2. 남은 숫자가 음수라면, 조합을 만드는 것이 불가능하다는 뜻으로 0을 반환시킨다.

3. dp테이블에 값이 있다면, 그 값을 반환한다.

 

남은 숫자만큼의 값을 만들기 위한 경우의 수를 담기 위해 currentCombination 변수를 만든다.

반복문을 하나 만들어서

남은 숫자 = 지금 남은 숫자 - 반복문 요소의 수로 정하고, 재귀 함수 연산을 시킨 값을 currentCombination에 누적시킨다.

 

dp[남은 목표값]에 currentCombination을 저장시키고, 반환시킨다.

 

코드

C++

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> dp;

    int countCombinations(vector<int>& nums, int remainingTarget) {
        if (remainingTarget == 0)
            return 1;

        if (remainingTarget < 0)
            return 0;

        if (dp[remainingTarget] != -1)
            return dp[remainingTarget];

        int currentCombinations = 0;

        for (int i = 0; i < nums.size(); i++) {
            int currentNum = nums[i];
            currentCombinations += countCombinations(nums, remainingTarget - currentNum);
        }

        dp[remainingTarget] = currentCombinations;
        return currentCombinations;
    }

    int combinationSum4(vector<int>& nums, int target) {
        dp.assign(target + 1, -1);
        return countCombinations(nums, target);
    }
};