[프로그래머스]깊이/너비 우선 탐색(DFS/BFS) : 타겟 넘버 (level 2)(java, c++)

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

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

 

java 코드

class Solution {
 
    int answer;
 
    public int solution(int[] numbers, int target) {
        boolean[] flag = new boolean[numbers.length];
        answer = 0;
        
        // 배열의 멱집합 구하기
        powerSet(numbers, flag, 0, target);
        return answer;
    }
 
    public void powerSet(int[] numbers, boolean[] flag, int depth, int target) {
 
        if (depth == numbers.length) {
            int iSum = 0;
            
            // flag값이 true면 + , flase 면 -
            for (int i = 0; i < depth; i++) {
                if (flag[i] == true) {
                    iSum += numbers[i];
                } else {
                    iSum -= numbers[i];
                }
            }
 
            if (iSum == target) {
                answer++;
            }
            return;
        }
 
        flag[depth] = true;
        powerSet(numbers, flag, depth + 1, target);
 
        flag[depth] = false;
        powerSet(numbers, flag, depth + 1, target); 
    }
}

 

c++ 코드

#include <vector>

using namespace std;

int cnt;

void dfs(const vector<int> &numbers, int sum, int i, const int &target)
{
    if (i == numbers.size())
    {
        if (sum == target)
        {
            cnt++;
        }
        return ;
    }

    dfs(numbers, sum + numbers[i], i + 1, target);
    
    dfs(numbers, sum - numbers[i], i + 1, target);
}

int solution(vector<int> numbers, int target) {
    
    dfs(numbers, 0, 0, target);

    return cnt;
}

 

java코드 

멱집합 구하기를 이용해서 풀었다

(멱집합 구하는데 쓰인 알고리즘을 "백트랙킹"이라고 하는 것 같다.) 

백트랙킹 공부하면 다시 업뎃하겠다...

 

(20200508 추가)

c++코드

DFS로 풀었다.

예전에 풀었던 java코드랑 비교하니, c++코드가 훨씬 깔끔하다.