2/6 타겟넘버

[skarltjr]

package algo;


/**
 * 주어진 numbers들로 target을 만드는 방법 수를 리턴
 * */
public class Solution {
    int ans = 0;
    public int solution(int[] numbers, int target) {
        int count = 0; // 수행한 numbers 중 숫자 개수 . 이게 length랑 같으면 종료
        int total = 0; // 총합이 target이면 정답


        //  (+/-) ㅁ (+/-) ㅁ (+/-) ㅁ ....
        // +일때
        bfs(numbers,total+numbers[0],target,count+1);
        // -일때
        bfs(numbers,total-numbers[0],target,count+1);


        return ans;
    }

    public void bfs(int[] numbers,int total, int target, int count)
    {
        if (count == numbers.length)
        {
            if (total == target) {
                ans++;
                return;
            }else {
                return;
            }
        }

        bfs(numbers, total + numbers[count], target, count + 1);
        bfs(numbers, total - numbers[count], target, count + 1);
    }

}