프로그래머스 - 타겟 넘버

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> numbers, int target) {
    int answer = 0;
    vector<bool> oper(numbers.size(), false);
    int len = numbers.size();
    sort(numbers.begin(), numbers.end());
    for(int i=0; i<=len; i++)
    {
        std::fill(oper.begin(), oper.end(), false);
        std::fill(oper.end() - i, oper.end(), true); //false -> (-)
        do{
                int num = 0;
                for(int i=0; i<numbers.size(); i++)
                {
                    int minus = (!oper[i]) ? -1 : 1;
                    num += (numbers[i] * minus);
                }
                if (target == num)
                    answer++;
        }while(next_permutation(oper.begin(), oper.end()));
    }
    return answer;
}

재귀로 푼 코드

#include <string>
#include <vector>
 
using namespace std;
 
int total;
 
void DFS(vector<int> &numbers, int &target,int sum,int n) {
    if(n >= numbers.size()){
        if(sum == target) total++;
        return;
    }
 
    DFS(numbers, target, sum + numbers[n], n+1);
    DFS(numbers, target, sum - numbers[n], n+1);
}
 
int solution(vector<int> numbers, int target) {
    int answer = 0;
 
    DFS(numbers, target, numbers[0] , 1);
    DFS(numbers, target, -numbers[0], 1);
 
    answer = total;
 
    return answer;
}

재귀로 깔끔하게 푸는 연습을 하자!