Level 2
n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
numbers | target | return |
---|---|---|
[1, 1, 1, 1, 1] | 3 | 5 |
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int dfs(int index, vector<int> numbers, int sum, int target) {
if(index >= numbers.size()) {
if(sum == target) {
return 1;
} else {
return 0;
}
}
int tmpSum1 = sum + numbers[index];
int tmpSum2 = sum - numbers[index];
int tmpAnswer = 0;
tmpAnswer += dfs(index+1, numbers, tmpSum1, target);
tmpAnswer += dfs(index+1, numbers, tmpSum2, target);
return tmpAnswer;
}
int solution(vector<int> numbers, int target) {
int answer = 0;
answer += dfs(1, numbers, numbers[0], target);
answer += dfs(1, numbers, -numbers[0], target);
return answer;
}