조합(combination) 알고리즘 1. 중복조합

                                    # 참고사항
📜 n의 크기는 최대 30
📜 하나의 후보를 중복해서 사용해도 상관없다. - 제한없이 중복가능
☠️ target이 될 수 없다면 []출력

                                    🤔 가능한 모든 조합을 하나씩 고려한다면?
👉 시간복잡도가 O(n!)이라 통과가 안될 것이다.

🤔 BFS로 풀어보자.
♟️ nums를 만들어서 하나씩 넘긴다

♟️ 가장 최소부터 가장 최대까지 하나씩 모두 연산 수행
👉 중복을 포함해야 한다.

♟️ target값이 음수 혹은 최소값 보다 작아진다면 return

♟️ target이 0이 되면 nums를 result에 넣기 - 중복 체크하기.

                                    import copy
from collections import Counter

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []

        def isUnique(arr):
            for res in result:
                print("unique check")
                if Counter(res) == Counter(arr):
                    return False
            return True

        def bfs(nums, acc):
            print(">>> bfs <<<")
            print("bfs start: nums, acc : {}, {}".format(nums, acc))
            for candidate in candidates:
                print("in bfs: now: {}, candidate: {}".format(nums, candidate))
                test_nums = nums[:]
                test_nums.append(candidate)
                test = acc
                test += candidate

                if test > target:
                    print("acc is over target: discarded !, test > target : {} > {}".format(test, target))
                    continue

                if test == target:
                    arr = test_nums[:]
                    if isUnique(arr):
                        result.append(arr)
                        print("result added, result: {}".format(result))
                    continue

                # acc < target
                bfs(test_nums, test)

        bfs([], 0)

        return result

                                    🤔 기본적으로 중복 체크에서 O(n * k)의 시간 복잡도가 들기 때문에, O(n²)까지는 봐줄만 할 것 같다.
>>> ❌❌❌

🤔 중복 체크를 없애는 방법을 고려해야 한다.

📌 순열과 조합은 현실적으로 exponential보다 작은 시간복잡도를 구할 수 없다.
✅ 하지만, 주어진 환경 내에서는 최대 효율을 구하는 방법을 물어본다.
>>>

♟️핵심은 ➡️정렬이다
>>> 각 조합을 정규화(canonical) 된 순서로만 생성하도록 하는 것이 핵심이다.
    >>> 생성 조합은 항상 오름차순만 가능하다.
        >>> [1, 2, 1], [2, 1, 1]과 같은 경우가 고려되지 않는다.

✅ 각 track에 start pointer가 필요하다.
>>> for문을 시도할 때 start >= 인 경우만 보면된다.

                                    import copy
from collections import Counter

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        candidates.sort()

        def dfs(nums, start, acc):
            for i in range(start, len(candidates)):

                if start >= len(candidates):
                    return

                candidate = candidates[i]
                t_start = i
                t_acc = acc + candidate
                t_nums = nums[:] + [candidate]

                if t_acc > target:
                    return

                if t_acc == target:
                    result.append(t_nums)

                dfs(t_nums, t_start, t_acc)

        dfs([], 0, 0)

        return result