알고리즘 문제 풀이/프로그래머스
[프로그래머스] 타겟 넘버 c++
부끄러엇피치
2022. 3. 18. 20:11
728x90
출처: 프로그래머스
https://programmers.co.kr/learn/courses/30/lessons/43165?language=cpp
코딩테스트 연습 - 타겟 넘버
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수
programmers.co.kr
#include <string>
#include <vector>
using namespace std;
int answer = 0;
void dfs(vector<int> numbers, int target, int total, int index){
if (index == numbers.size()){
if (total == target){
answer ++ ;
}
return;
}
dfs(numbers, target, total + numbers[index], index + 1);
dfs(numbers, target, total - numbers[index], index + 1);
}
int solution(vector<int> numbers, int target) {
dfs(numbers, target, numbers[0], 1);
dfs(numbers, target, -numbers[0], 1);
return answer;
}