[LeetCode] 377. Combination Sum 4 (C++)

문제

 

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

Combination Sum IV - LeetCode

 

풀이

 

난이도: Medium 

 

배열의 원소의 합이 target이 되는 조합을 구하는 문제.

조합을 구성하는 원소가 같더라도 순서가 다르다면 다른 조합으로 취급하기 때문에 조금 까다로웠다.

 

처음에는 dp[value]를 value를 만들 수 있는 조합의 수라고 할 때 

dp[value] = dp[nums] * dp[value - nums]로 모든 조합을 구할 수 있다고 생각했는데,

이러한 점화식의 문제점이 있다.

 

nums = [1,2]라고 하고 target이 7이라고 하자.

dp[7]은 아래의 모든 경우의 수를 더하게 된다.

dp[7] += dp[1] + dp[6]

dp[7] += dp[2] + dp[5]

dp[7] += dp[3] + dp[4]

dp[7] += dp[4] + dp[3]

.

.

.

이때 nums에는 1이 존재하므로 모든 dp[value]값은 1만으로 이뤄진 조합이 존재할 것이다.

dp[1] = [1]

dp[2] = [1, 1]

dp[3] = [1, 1, 1]

.

.

.

따라서 위의 점화식은 항상 중복된 조합을 포함하게 된다.

 

 

그래서 중복을 피하고자 떠올린 방법이 

dp[value]의 value를 nums와 value - nums로 두 부분으로 나누고 nums는 단 하나의 원소 값으로 고정한다.

dp[value] += dp[value - nums]  => [nums,  (value - nums)의 조합들]

 

예를 들어 Input: nums = [1,2,3], target = 4 인 경우,

dp[4]는 아래와 같이 구할 수 있다.

 

dp[4] += dp[3] (nums는 1로 고정)

(1, 1, 1, 1)

(1, 1, 2)

(1, 2, 1)

(1, 3)

 

dp[4] += dp[2] (nums는 2로 고정)

(2, 1, 1)

(2, 2)

 

dp[4] += dp[1] (nums는 3로 고정)

(3, 1)

 

이처럼 조합의 가장 앞 원소를 nums의 특정 값으로 고정하여 중복된 조합을 피할 수 있다.

 

단, 문제에서는 정답을 32-bit integer로 제한한다고 했지만 사실 dp[target]의 값만 32-bit integer 로 제한되고, 

target이하의 값에서는 overflow가 발생하는 테스트 케이스가 있다.

따라서 나머지 연산을 통해 overflow의 발생을 막아주었다.

 

 

 

 

코드