문제

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

문제 설명

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 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1
문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

총 2가지 방법이 있으므로, 2를 return 합니다.

---

Approach #1

+1 -> +1 -> +1 -> +1 -> +1 (5)
                     -> -1 (3) v
               -> -1 -> +1 (3) v
                     -> -1 (1)
         -> -1
   -> -1
-1

+4 ->
-4

dfs로 풀면 되겠다.

numbers의 element들을 보면서 가능한 모든 경우의 연산을 해본다.(dfs이용)
한 연산 종료시 계산된 결과를 target과 비교하고, 같으면 cnt ++해줌.

Solution #1

function solution(numbers, target) {
    var answer = 0;
    dfs(numbers, 0, 0);

    function dfs(numbers, numIdx, sum){
        if(numIdx === numbers.length){
            if(sum === target) answer++;
            return;
        }
        dfs(numbers, numIdx+1, sum+numbers[numIdx]);
        dfs(numbers, numIdx+1, sum-numbers[numIdx]);
    }
    return answer;
}

N: numbers.length

Time Complexity

O(2^N)

2 * 2^N 번만큼 dfs 함수 실행됨

Space Complexity

O(N) for call stack

콜스택에 쌓인 dfs함수중 가장 재귀가 깊게 들어가는건 N만큼.

Review

문제 읽고 dfs로 풀자! 코드 샥샥 짜고 통과됐을때 너무 기뻤다. ㅠ.ㅠ
3달전보단 훨씬 많이 는거 같아서 뿌듯 ㅎ.ㅎ

---

Approach #2

위 코드 리팩토링 해야할듯!

Solution #2

function solution(numbers, target) {
    let answer = 0;
    dfs(0, 0);
    function dfs(level, sum){
        if(level === numbers.length){
            if(sum === target) answer++;
            return;
        }
        dfs(level+1, sum+numbers[level]);
        dfs(level+1, sum-numbers[level]);
    }
    return answer;
}