82 문제와 매우 비슷하지만, #82 는 combination의 개수를, 이번 문제는 permutation의 개수를 구하는 문제이다.
따라서 이번 문제에서는 중복을 허용해야 한다!
이를 위해서 (1D DP 풀이법 기준) #82 문제에서 for문 중첩 순서를 반대로 하면 된다.
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target + 1):
for num in nums:
if i >= num:
dp[i] += dp[i - num]
return dp[target]
Approach
82 문제와 매우 비슷하지만, #82 는 combination의 개수를, 이번 문제는 permutation의 개수를 구하는 문제이다.
따라서 이번 문제에서는 중복을 허용해야 한다!
이를 위해서 (1D DP 풀이법 기준) #82 문제에서
for문 중첩 순서를 반대로 하면 된다.Complexity
O(n * target)O(target)