[JAVA] 구현_타겟넘버(Level 2)

P.505

링크텍스트

import java.util.Stack;

public class Solution {
    private static class State {
        public final int index;
        public final int acc;
        
        State(int index, int acc) {
            this.index = index;
            this.acc = acc;
        }
    }
    public int solution(int[] numbers, int target) {
        Stack<State> s = new Stack<>();
        s.push(new State(0, 0));
        
        int count = 0;
        
        while (!s.isEmpty()) {
            State state = s.pop();
        
            if (state.index == numbers.length) {
                if (state.acc == target) count++;
                continue;
            }
            
            s.push(new State(state.index + 1, state.acc - numbers[state.index]));
            s.push(new State(state.index + 1, state.acc + numbers[state.index]));
        
        }
        
        return count;
    }
}