[LeetCode 풀이/python] 39. Combination Sum (medium)

문제 설명: 구분되는 (중복이 없는) 정수 값으로 이루어진 배열 candidates 과 타겟 값 target 이 주어졌을 때, candidates 에서 선택한 숫자들을 더하여 타겟 값이 될 수 있는 고유한 숫자 조합을 모두 담은 리스트를 리턴하시오. 리스트 내 조합의 순서는 무관하며, candidates 에서 동일한 숫자가 선택될 수 있는 횟수에는 제한이 없다. 두 숫자 조합에서 선택된 숫자들 중 최소 하나라도 사용된 빈도가 다른 경우 이들은 고유 조합으로 간주된다. 주어진 입력에 대해 가능한 고유 숫자 조합의 개수는 150개를 넘지 않음이 보장된다.

 

(Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.)

 

예시 1)

입력: candidates = [2,3,6,7], target = 7  -->  출력: [[2,2,3],[7]]

설명: 2와 3을 조합해서 2+2+3=7 , 7을 조합해서 7 = 7

 

예시 2)

입력: candidates = [2,3,5], target = 8  -->  출력: [[2,2,2,2],[2,3,3],[3,5]]

 

예시 3)

입력: candidates = [2], target = 1  -->  출력: []

 

예시 4)

입력: candidates = [1], target = 1  --> 출력: [[1]]

 

예시 5)

입력: candidates = [1], target = 2  --> 출력: [[1,1]]

 

제한 조건:

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidates 의 모든 원소는 각기 구별됨(distinct, 중복X)
• 1 <= target <= 500

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 타겟 값을 업데이트 & 탐색 범위를 줄여가면서 재귀적으로 풀면 될 것 같은데 정확하게 구현을 못해서 한참 씨름하다가...
  • 백트래킹 알고리즘을 활용하면 쉽게 풀리는 문제라는걸 알게 됨 ㅇ_ㅇ
  • 기본적으로 깊이 우선 탐색(DFS) 알고리즘을 기반으로 탐색하되,
    • 조건에 맞게 탐색 범위와 타겟 값을 업데이트 & 조건을 만족하는 경로를 기록해둠
    • 제한 조건을 만족하지 않아서 더 깊이 탐색할 필요가 없으면 멈추고 이전에 왔던 길로 되돌아 감
    • 탐색 끝에 완결 조건에 도달하면 해당 경로(path) 를 저장 + 이전 길로 돌아가 추가적인 가능 경로 탐색

 

• 코드 구현

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    res = []
    dfs(candidates, target, [], res)
    return res

def dfs(nums, target, path, res):
    for i in range(len(nums)):
        if target == 0:
            res.append(path)
            return False
            
        elif target < 0:
            return False
            
        else:
            dfs(nums[i:], target-nums[i], path+[nums[i]], res)

 

• 결과
  • 가장 기본적인(?) 백트래킹 알고리즘을 적용했더니 런타임이 꽤 오래 걸림...
  • 탐색 경로를 출력해보니 불필요한 탐색이 이루어지는 경우가 발생  ->  되돌아가는 조건을 좀더 precise 하게...! 

 

[풀이 2안]

• 접근법
  • 1안의 알고리즘에서 단순히 target 값이 negative 일 때 뿐 아니라, candidates 의 어느 숫자로도 만들어낼 수 없는 경우 더 이상 탐색을 진행할 필요가 없음
    • 곧, candidates 의 숫자 중 가장 작은 수(min_int) 보다 target 값이 작은 경우!

 

• 코드 구현

def combinationSum(candidates, target):
    res = []
    min_int = sorted(candidates)[0]
    dfs(candidates, target, min_int, [], res)
    return res

def dfs(nums, target, min_int, path, res):
    for i in range(len(nums)):
        if target == 0:
            res.append(path)
            return False
        else:
            if target < min_int:
                return False
            dfs(nums[i:], target-nums[i], min_int, path+[nums[i]], res)



• 결과
  • 불필요한 추가 탐색을 줄여 런타임이 크게 줄었다 야호 ~_~