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

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

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

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

풀이

타겟 넘버를 만들기 위해서는 주어진 숫자의 부호를 +나 -로 정해서 모든 경우의 수를 다 해봐야 답을 알 수 있다. 그 모든 경우를 구하는 것을 나는 조합으로 생각했다. [1,2,3,4,5] 라고 입력이 주어진다면 이 중 하나 선택하는 경우 [1],[2],[3],... 일 경우 선택된 숫자들의 부호만 -를 붙여준다. 이런 식으로 0개를 고르는 경우부터 5개를 고르는 경우 모두 다 한다면 그 안에서 타겟 넘버가 만들어지는 경우를 count할 수 있다.

그래서 조합을 구현하였는데, 조합은 하나의 수를 두고 선택하는 경우, 그리고 선택하지 않는 경우 모두 재귀 호출을 한다. 하지만 선택했는지 안했는지는 알려야하기에 파라미터로 그 여부를 받는다. 그렇게 모두 선택했으면 계산하여 타겟 넘버가 되는지 확인하고 된다면 전역변수인 count의 값을 증가시켜서 답을 구할 수 있다.