leetcode 39. Combination Sum
백트래킹(Back tracking)
백-트래킹은 단어 그대로 다시 돌아가서 체크한다는 뜻이다. 완전 탐색을 하는 도중에 길을 잘못 들은 게 확실해졌을 때, 즉 여기서부터는 탐색을 하지 않아도 될 때 이전으로 돌아가서 다른 부분을 탐색하도록 한다.
Tree를 탐색할 때 포함되면 안되는 값이 나왔을 경우 그 밑으로는 탐색을 아예 하지 않는 경우를 생각해볼 수 있다.
DFS의 백트래킹
DFS는 한번 길을 잡으면 leaf 까지 갔다가 다음 길을 탐색한다. (Depth-first) 그래서 중간 지점에서 이 길이 잘못된 길이라는 걸 파악하게 되면 아래쪽을 하나도 탐색하지 않아도 된다. 끊어주자.
Question
unique한 값들로 이뤄진 candidates에서 숫자를 sampling with replacement 해서 target을 만들 수 있는 모든 경우를 찾기
Solution
기본적으론 완전 탐색을 진행한다. 각 candidates의 숫자들이 등장할 수 있는 최대의 개수를 구한 후 그 범위 안에서 모든 경우를 탐색해본다. 범위를 어떻게 좁힐 수 있느냐? 백트래킹을 어떻게 적용할 수 있느냐? 가 관건이다.
Solution 1
처음에는 매우 무식/단순하게 진행해보았다. 모든 candidates들의 최대 등장 횟수를 동일하게 구했다. 가장 작은 값이 등장할 수 있는 횟수로 통일했다.
그리고 sampling with replacement 방식으로 모든 경우를 나열한 후에 가능한 경우를 추려냈다.
def sol1(candidates: List[int], target: int):
max_n = target // min(candidates)
pool = list(product(range(max_n+1), repeat=len(candidates)))Candidates가 [2,3,6,7]이고 target=7이라면, 최소값 2 기준으로 최대 3회 등장하기 때문에 모든 candidates들의 최대 등장 가능 범위가 0~3이 된다. [3, 0, 0, 0]은 [2,2,2]를 뜻한다. 2만 세 번 등장했다는 뜻이다.
나머지 코드는 github에서 확인 가능하다.
Solution 2
사실 이 코드도 완전히 효율적이진 않다. 다만 탐색의 범위를 좁혔고 (이것 만으로 통과할 수 없었다) 중간에 백트래킹 방식을 도입함으로서 겨우 통과할 수 있었다.
각 candidates 값들이 가질 수 있는 최대값을 다르게 정의한다. 그 범위 안에서 탐색하는데 중간에 target을 넘어가는 상황이 발생하면 탐색을 종료하고 다른 길을 탐색한다. (백트래킹) 아래 코드에는 단순 DFS가 아닌 중간중간 탐색을 종료하고, 효율성을 높여줄 수 있는 장치들을 넣었다. (아래 코드의 주석 참고)
우선 장치1은 백트래킹을 위한 내림차순 정렬이다. 가장 큰 수부터 탐색한다면, target을 넘어서는 경우를 좀 더 빠르게 접하게 될 것이다. 넝머가면 바로 종료하면 된다.
장치2는 조기 종료 부분이다. 현재까지의 path로만 봐도 이미 target 값을 초과했다면 다음 값들과 관계 없이 이미 invalid하다.
장치3은 작은 부분인데 O(num_candidates)로 이뤄지는 transform 연산을 조금이나마 줄이기 위한 장치이다.
def sol2(candidates, target):
ans = list()
candidates.sort(reverse=True) # 장치 1
max_n = [target//i for i in candidates]
def transform(path):
nonlocal candidates
rst = list()
for i in range(len(path)):
rst += [candidates[i]] * path[i]
return rst
def dfs_helper(path, idx, val):
nonlocal candidates, max_n, ans, target
trans = transform(path)
sum_trans = sum(trans)
if sum_trans > target: return # 장치 2
path.append(val)
sum_trans += (candidates[idx]*val) # 장치 3
trans += [candidates[idx]] * val
if len(path) == len(candidates):
if sum_trans == target:
ans.append(trans)
return
togo = list(range(max_n[idx+1]+1))
for loc in togo:
dfs_helper(path[:], idx+1, loc) # 포인트 1추가적으로 하나의 학습 포인트가 더 있다. DFS 돌 때 한번 leaf 까지 갔다가 돌아왔는데도 특정 변수가 leaf 때의 값을 기억하고 있어서 다른 경로 탐색이 어려운 경우가 있다.
예를 들어, [0,0,0]에서 0, 1로 갈 수 있는 갈림길이 있다고 하자. 그리고 path에 원소 4개가 쌓이면 더 이상 길은 없다.
우선 0으로 가면 path에 [0,0,0,0] 값이 할당된다. 그리고 최종적인 판단 (합이 target과 같은지)을 한 후 다시 갈림길로 돌아와 1을 탐색해야 한다.
이 때 path는 [0,0,0,0]이 아닌 [0,0,0]에서 1로 들어서야 하는데, 이미 path에는 [0,0,0,0]이 할당돼버려서 1을 탐색하게 되면 [0,0,0,0,1]이 되고 만다.
위 코드의 포인트1 부분으로 해결했다. 하나의 for loop 안에서는 고정된 path 값들을 갖게 하기 위해서 path[:]로 copy한 것이다. [0,0,0,0]을 갔다 오더라도, 다음 for iter에서도 다시 [0,0,0]인 상태의 파라미터가 들어갈 수 있다.
모든 코드는 -> github
좋은 효율성은 아니었다...
