[백준 알고리즘 -1182] 부분집합의 합 - java(재귀호출/부제:오랜만에 삽질일기)

아 너무 삽질했다 ㅠ__ㅠ

부분 집합을 하나하나 구하는 것이기 때문에

 현재까지의 합이 S와 일치하더라도 해당 호출을 종료하는 것이 아니라

count 계속 탐색해야한다.

여기에 너무 꽂힌 나머지 종료 조건을 잘못 생각하고 삽질 했다.

현재 검색하는 index를 선택할지 선택하지 않을지를 구분하여 재귀호출을 하고

함수의 맨 윗부분에 if(cur == S) 조건을 달아주었는데,

생각해보니 이렇게 하고 나서 if( idx >= arr.length) 조건을 통해 종료한 뒤 다시 저 조건으로 들어가 중복되어 세지는 문제가 발생하였다.

사실 굳이 호출하면서 바로바로 cur과 S를 비교해주지 않아도 결국 arr 끝까지 오면 그 모든 경우를 들어가는 것인데 말이다 ㅠ__ㅠ 

arr의 모든 idx를 고려했을 때(선택할지/선택하지 않을지)

OOOOOO

OOOOOX

OOOOXO

OOOOXX ...

.. 중략

이렇게 모든 경우가 세어지는데, 나는 이걸 간과하고 

OOO -> cur==SUM 이면 count++ 이렇게 해버리고 나중에

모든 idx를 고려했을 때

OOOXXX -> 이 경우에 count++ 가 되어버렸으니 당연히 틀릴 수밖에

아 반성의 시간이 길었닼ㅋㅋㅋㅋㅋㅋ 왜냐면 정말 별문제 아닌데 삽질을 너무 오래해서 억울함 ㅠ__ㅠ 

그럼 코드 

import java.util.Scanner;

class Main{
		static int max=0;
		static public void set(int[] arr, int S,int cur, int idx, int count) {
			if(idx>=arr.length)
			{
                if(cur==S && count>0)
                    max++;
				return;
			}
            
			//현재 인덱스를 포함한다
			set(arr, S, cur+arr[idx], idx+1, count+1);
			
			
			//포함하지 않는다
			set(arr, S, cur , idx+1, count);

		}
       public static void main(String[] args){
    	   Scanner scan=new Scanner(System.in);
    	   int N=scan.nextInt();
    	   int S=scan.nextInt();
    	   
    	   int[] arr=new int[N];
    	   for(int i=0; i<N; i++) {
    		   arr[i]=scan.nextInt();
    	   }
    	   set(arr, S, 0, 0,0 );

    		   System.out.println(max);


       }
       
       
}