1182_부분수열의 합 (JAVA)

1182번: 부분수열의 합

import java.util.Scanner;

public class Main {
	static int S;
	static int ans = 0;
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		S = sc.nextInt();

		int[] num = new int[N];
		boolean[] checked = new boolean[N];
		for(int i=0; i<N; i++){
			num[i] = sc.nextInt();
		}

		makeset(num, checked, 0, 0); //부분집합
        
		System.out.println(ans);
	}

	private static void makeset(int[] num, boolean[] checked, int index, int sum){
		if(index>=num.length){
			if(sum==S){
				int cnt = 0; //공집합인 경우 제외하기 위해 cnt 사용
				for(int i=0; i<num.length; i++){
					if(checked[i])
						cnt++;
				}
				if(cnt>0)
					ans++;
				return;
			}
			else return;
		}

		checked[index] = false; //num[index] 포함X
		makeset(num, checked, index+1, sum);

		checked[index] = true; //num[index] 포함O
		makeset(num, checked, index+1, sum+num[index]);
	}
}

 

1. 재귀함수를 이용해 부분집합을 구한다.

 

   이때, 해당 인덱스의 값이 포함되면 - sum+num[index] 로 인자를 넘겨주고,

   해당 인덱스의 값이 포함되지 않는다면 원래의 sum값을 인자로 넘겨준다.

 

 

2. index>=num.length 즉, num[0]~[num.length-1]까지 탐색을 완료했다면, sum==S인지 확인한다.

 

   문제 예시 - {-7, -3, -2, 5, 8}, S=0 의 경우를 예시로 들어보면

   sum==S 인 경우는 2가지가 나온다 : {-3,-2,5}, 공집합

   공집합의 경우를 제외해주어야 하기 때문에, if(checked[i])인 경우를 cnt로 세고, cnt>0인 경우에 답으로 판단한다.

 

 

 

부분집합