참고
문제해설
문제 로직고민
NOTE
•
가장 단순한건 모든 수식의 경우를 계산하는 방법이다.
◦
모든 숫자는 +/- 의 경우를 가지므로, 완전이진트리 형식의 높이21인 트리가 나올거다.
◦
2^21만큼의 탐색은 상당히 높은게 아닐까 생각했지만, 200만 정도의 수준이었다.
작성코드
NOTE
class Solution {
int result;
int[] numbers;
int target;
public int solution(int[] numbers, int target) {
this.numbers = numbers;
this.target = target;
this.result = result;
dfs(0, 0);
return result;
}
private void dfs(int step, int sum){
if(step == numbers.length) {
if(sum == target) result++;
return;
}
dfs(step + 1, sum + numbers[step]);
dfs(step + 1, sum - numbers[step]);
}
}
Java
복사
다른사람 풀이
NOTE
class Solution {
public int solution(int[] numbers, int target) {
int answer = 0;
answer = dfs(numbers, 0, 0, target);
return answer;
}
int dfs(int[] numbers, int n, int sum, int target) {
if(n == numbers.length) {
if(sum == target) {
return 1;
}
return 0;
}
return dfs(numbers, n + 1, sum + numbers[n], target) + dfs(numbers, n + 1, sum - numbers[n], target);
}
}
Java
복사
재귀방식을 더 깔끔하게 호출하는 방법