🖊️ 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165

---

🖊️ 풀이

완전 DFS의 정석같은 문제!
DFS문제를 자주 접하지는 않았지만 옛날옛적에.. 연산자 끼워넣기 풀었던 기억이 바로 났다
이런 식으로 모든 조합을 구해서 조건에 맞는 경우의 수를 찾는 느낌?

DFS를 통해서 numbers의 각 원소들의 +/- 값들을 더해보고,
최종 값이 target과 같으면 answer++해주면 되는 간단한 문제!

재귀함수를 통해서 DFS를 구현했다.

아래는 내가 제출했던 코드
그치만 제출하고 나서 다른 분 코드 보고 깨달은 점..
무지성으로 vector를 복사대입했다.
벡터의 레퍼런스를 함수의 인자로 넘기는 방식으로 하는건 어떨까?
이런거 하나하나 생각해보는게 좋을 것 같다!

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

using namespace std;

int answer = 0;
vector<int> nums;

// DFS
void GetNum(int curNum, int idx, int target, int size) 
{
    if (idx == size - 1) {
        if (curNum == target) {
            answer++;
        }
        return;
    }
    GetNum(curNum + nums[idx + 1], idx + 1, target, size);
    GetNum(curNum - nums[idx + 1], idx + 1, target, size);
}

int solution(vector<int> numbers, int target) {    
    nums = numbers;
    
    GetNum(nums[0], 0, target, numbers.size());
    GetNum(-nums[0], 0, target, numbers.size());
   
    return answer;
}

아래가 내가 풀었던 것 (복사 생성)
위가 참조자를 넘겨준 것
다른 분들은.. 나처럼 복사생성 무식하게 한 분은 없던데
왜 시간도,, 공간도.... 이럴까?
이건 탐구필요하겟다 ..