ALGORITHM
[JAVA] [프로그래머스] Level 2 - DFS/BFS - 타겟 넘버
printf100
2020. 10. 19. 16:50
programmers.co.kr/learn/courses/30/lessons/43165
코딩테스트 연습 - 타겟 넘버
n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+
programmers.co.kr
class Solution {
int answer = 0;
public int solution(int[] numbers, int target) {
dfs(numbers, 0, 0, target);
return answer;
}
public void dfs(int[] numbers, int index, int sum, int target) {
if(numbers.length == index) {
if(target == sum)
answer++;
}
else {
dfs(numbers, index + 1, sum + numbers[index], target);
dfs(numbers, index + 1, sum - numbers[index], target);
}
}
}