[프로그래머스 Programmers] 타겟 넘버

문제 설명

문제 링크

정수들의 순서를 바꾸지 않고!
적절히 더하거나 빼서 (양수 또는 음수로써 주어진 배열 내의 숫자를 백트래킹 하여) target number와 같은 수를 만들도록 하는 방법의 수를 찾아내는 문제이다.

생각 정리

//height랑 numbers.length 똑같으면 
        //이 때, target과 더해진 숫자가 같으면 방법의 수 ++
        // 리턴한다.
    //numbers 배열 순회하면서
        //방문안했으면
            //방문처리하고
            //dfs재귀 ( + )
            //방문처리해제
            //dfs재귀 ( - )
            //방문처리해제

정리된 생각에 대한 논리

나는 이 문제가 잘 안풀렸다. 내가 어려움을 겪은 부분은 "정수들의 순서를 바꾸지 않고"
target 넘버와 같은 결과를 만들어내는 것이다.

• 정수들의 순서를 바꾸지 않기 위해
  - height와 numbers 배열 내에서 해당 숫자의 idx를 비교했다.
  • height와 idx가 같을 때 (정수들의 순서는 바꾸지 않고)
  • 방문처리와 dfs재귀를 이어갔다.

완성

class Solution {
    static int method = 0;
    static boolean[] visited;
    static int[] arr;
    public int solution(int[] numbers, int target) {
        
        visited = new boolean[numbers.length];
        arr = new int[numbers.length];
        
        dfs(numbers, target, 0);
        return method;
    }
    
    static void dfs(int[] numbers, int target, int height) {
        if(height == numbers.length){
            int sum = 0;
            for(int i=0; i<height; i++){
                sum += arr[i];
            }
            
            if(sum == target){  
                method++;   
            }
            return ;
        }
        
        
        for(int i=0; i<numbers.length; i++) {
            if(!visited[i]) {
                if(height == i){
                    visited[i] = true;
                    arr[height] = numbers[i];
                    dfs(numbers, target, height+1);
                    visited[i] = false;
                    arr[height] = -numbers[i];
                    dfs(numbers, target, height+1);
                    visited[i] = false;
                }
                
            }
        }
    }
}