프로그래머스_DFS/BFS_타겟 넘버

문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.     사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.    제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

 

다시 쉬어가는 문제입니다. 주어지는 배열의 숫자들이 음수일 경우와 양수일 경우의 모든 조합을 해서 target과 일치하면 됩니다.

 

배열의 특정 값 입장에서 순서가 유효하지 않도록(원소 중복이 없도록) "내가 양수일 경우"와 "내가 음수일 경우"의 모든 경우의 수를 구하는 모양새가 어디서 많이 본 것 같습니다. 멱집합을 구하는 방식입니다. 원래 visit 배열에서 true, false로 줬던 것을 이번엔 1, -1로 구분해주면 간단히 해결됩니다.

 

 

---

 

 

멱집합 구하기 알고리즘과 완전히 같은 구조이기 때문에 별도 설명은 생략하겠습니다. 혹시 처음 보시는 분들은 아래 링크를 참조하시면 됩니다.

 

[JAVA/- 알고리즘 및 자료구조] - 부분집합_재귀함수_멱집합 구하기 (JAVA)

 

package pojoPrj;

class Solution {
	
	private int count;
	
    public int solution(int[] numbers, int target) {
    	
    	int[] sign = new int[numbers.length];
    	Permutation(numbers, sign, 0, numbers.length, target);
        return count;
    }
    
    private void Permutation(int[] numbers, int[] sign, int index, int end, int target) {
    	
    	if (index == end) {
    		
    		int result = 0;
    		for(int i = 0; i < end; i++) {
    			
    			result += numbers[i] * sign[i];
    		}
    		
    		if(result == target) {
    			count++;
    		}
    		
    		return;
    	}
    	
    	sign[index] = 1;
    	Permutation(numbers, sign, index + 1, end, target);
    	
    	sign[index] = -1;
    	Permutation(numbers, sign, index + 1, end, target);
    }
    
}