조합과 순열

서로 다른 동전으로 목표합을 구하는 방법의 수를 구하는 문제이다. 다만, 하나는 같은 동전 조합이면 순서가 달라고 1가지로 치고(조합), 나머지는 순열을 구하는 문제이다.

조합문제

https://leetcode.com/problems/coin-change-2/

Coin Change 2 - LeetCode

 

순열문제

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

Combination Sum IV - LeetCode

 

답

loop의 순서를 바꾸면 답이 틀려버린다. 각 동전별로 과거 가능한 경우의 수를 쭉 더해 오는 것이 전자(조합), 각 액면별로 가능한 동전은 다 더해 오는 것이 후자(순열)이다.

class Solution:
    # combination
    def change(self, amount: int, coins: List[int]) -> int:
        table = [0] * (amount + 1)
        table[0] = 1
        
        for c in coins:
            for i in range(c, len(table)):
                    table[i] += table[i - c]
        
        return table[-1]
	
    # permutation
    def combinationSum4(self, coins: List[int], amount: int) -> int:
        table = [0] * (amount + 1)
        table[0] = 1
        
        for i in range(len(table)):
            for c in coins:
                if i - c >= 0:
                    table[i] += table[i - c]
        
        return table[-1]