접근
- 가능한 모든 케이스를 찾아야 하므로, 완전 탐색 유형이다.
- 시작을 0으로 하여 0번째 인덱스도 +/- 연산이 되도록 한다.
로직
- 너비 우선 탐색 (BFS)
- 큐에 0을 담는다.
- numbers에 대해 반복문을 돈다.
- queue에 담겨져 있는 모든 케이스에 대해서 새로운 정수를 더하거나/빼서 다시 큐에 넣어준다.
- 반복문 종료 이후, 필터링을 통해 타겟과 동일한 누적합만 남기고 길이를 반환한다.
-
- 깊이 우선 탐색 (DFS)
- 인덱스와 누적합 매개변수를 담을 수 있는 함수를 생성한다.
- 인덱스에 해당하는 값을 누적합에 더한 함수를 호출한다.
- 인덱스에 해당하는 값을 누적합에서 뺀 함수도 호출한다.
- 인덱스가 numbers의 크기와 같아졌을 때, 탐색을 끝낸다. 타켓 값과 누적합이 동일한 경우 result를 갱신한다.
코드
1. DFS 풀이
func solution(_ numbers:[Int], _ target:Int) -> Int {
var result = 0
func dfs(_ index: Int, _ sum: Int) {
if index == numbers.count {
if target == sum {
result += 1
}
return
}
dfs(index + 1, sum + numbers[index])
dfs(index + 1, sum - numbers[index])
}
dfs(0,0)
return result
}
2. BFS 풀이
def solution(numbers, target):
queue = [0]
for i in numbers:
update = []
for q in queue:
update.append(q + i)
update.append(q - i)
queue = update
return len(list(filter(lambda x: x == target, queue)))
