타겟 넘버

스택을 사용해 DFS로 풀었다. 근데 이렇게 하면 어떤 방식으로 값이 나왔는지는 알 수가 없다. 도착했는지 여부만 확인할 수 있다.

#include <string>
#include <vector>
#include <iostream>
#include <stack>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    //DFS 알고리즘 사용
    stack<pair<int, int>> st;
    int current_sum = 0, next_sum = 0, current_degree = 0, i;
    
    st.push({current_sum, current_degree});
    while(!st.empty()){
        current_sum = st.top().first;
        current_degree = st.top().second;
        st.pop();
        
        for(i = 0; i <= 1; i++){
            if(i == 0){
                next_sum = current_sum + numbers[current_degree];
            }
            else{
                next_sum = current_sum - numbers[current_degree];
            }
            if(current_degree + 1 == numbers.size()){
                if(next_sum == target){
                    cout << "target 도착\n";
                    answer++;
                }
                else{
                    ;
                }
            }
            else{
                st.push({next_sum, current_degree + 1});
            }
        }
    }
    
    return answer;
}

1번 방법을 최적화를 좀 하고, 경로를 확인 할 수 있도록 수정함

#include <string>
#include <vector>
#include <iostream>
#include <stack>
#include <tuple>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0, answer2 = 0;
    //DFS 알고리즘 사용
    stack<pair<int, int>> st;
    stack<tuple<int, int, string>> st2;
    int current_sum = 0, next_sum = 0, current_degree = 0;
    int current_sum2 = 0, next_sum2 = 0, current_degree2 = 0;
    string path, next_path;
    
    st.push({current_sum, current_degree});
    st2.push({0, 0, ""});
    
    
    // ------------- 1번 --------------
    while(!st.empty()){
        current_sum = st.top().first;
        current_degree = st.top().second;
        st.pop();
        
        if (current_degree == numbers.size()) {
            if (current_sum == target) {
                cout << "target도착\n";  // 경로 출력
                answer++;
            }
            continue;
        }
        
        next_sum = current_sum + numbers[current_degree];
        st.push({next_sum, current_degree + 1});
        next_sum = current_sum - numbers[current_degree];
        st.push({next_sum, current_degree + 1});
    }
    
    return answer;
    
    
     // ------------- 2번 --------------
    while(!st2.empty()){   
        tie(current_sum2, current_degree2, path) = st2.top();
        st2.pop();
        
        if (current_degree2 == numbers.size()) {
            // 모든 숫자를 사용했을 때 target인지 확인
            if (current_sum2 == target) {
                cout << "경로: " << path << " = " << target << "\n";  // 경로 출력
                answer2++;
            }
            continue;
        }
        
        // + 연산 추가
        next_sum2 = current_sum2 + numbers[current_degree2];
        next_path = path + (path.empty() ? "" : " + ") + to_string(numbers[current_degree2]);
        st2.push({next_sum2, current_degree2 + 1, next_path});

        // - 연산 추가
        next_sum2 = current_sum2 - numbers[current_degree2];
        next_path = path + (path.empty() ? "" : " - ") + to_string(numbers[current_degree2]);
        st2.push({next_sum2, current_degree2 + 1, next_path});
    }
    
    return answer2;
}