문제 이해

정수 수열이 주어졌을 때 수열의 합을 이용하는 문제이다.
부분 수열이 연속이여야 한다 등의 조건 없이 합이 S가 되기만 하면 되는 문제이다.

---

문제 풀이

부분 수열이 연속이라는 제한이 있었다면 DP 등을 통한 문제 해결을 고민해봤을 것이다.

하지만 부분 수열이 연속이 아니기 때문에, 이전에 계산했던 결과값이 무었이었든지 경우의 수는 지수적으로 증가한다는 것을 알게 되었다.

따라서 Brute-Force Algorithm을 활용하기로 했다.

이 때 한 번의 함수당 2번의 재귀함수를 호출하도록 식을 만들었다.

A라는 값이 수열에 포함되어 더해질 경우, 그리고 해당 값을 부분수열에 포함하지 않은 경우 모두를 재귀함수를 통해 인자로 넘겨주고 결과값을 확인하는 형식을 사용했다.

---

코드

import java.util.*;

public class Main {
	
	static ArrayList<Integer> list = new ArrayList<Integer>();
	static int N, S;
	static int answer = 0;
	
	public static void rec_fun(int value, int index, boolean real) {
        // value : rec_fun 재귀함수를 호출한 이전 재귀함수의 부분 수열 합
        // index : 부분 수열에 포함시킬지 아닐지 결정되어야 할 index
        // real : 부분 수열에 1개의 값 이상이 저장되어 있다면 true,
                  부분 수열이 공집합이라면 false 값을 가짐

		if(index==N) { // index = N이라는 것은 Array를 모두 확인했다는 의미.
			if(value==S && real) { 
            // value=S이고 공집합이 아니면 조건을 만족함
				answer++;
			}
			return;
		}
		rec_fun(value+list.get(index), index+1, true); 
        //부분수열에 data를 추가한 Case
		rec_fun(value,index+1, real);            
        //부분수열에 data를 추가하지 않은 Case
	}
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		S = sc.nextInt();
		sc.nextLine();
		String s = sc.nextLine();
		String[] tmp = s.split(" ");
		
		for(int i =0;i<N;i++) {
			list.add(Integer.parseInt(tmp[i]));
		}
		
		rec_fun(0, 0, false);
		
		System.out.println(answer);
	}
}

---

결과

• 1,2번째 틀린 이유는 동일한 코드를 제출하였기 때문이다.

• 틀린 이유 : boolean real을 활용하지 않았기 때문에 생긴 문제이다. 즉, 만약 내가 골랐던 수열이 공집합일 때, value = 0을 가지게 된다.
  하지만 공집합의 합은 존재하지 않기 때문에 null이 정확한 답이지 0은 정확한 답이 아니다. 따라서 공집합 문제를 해결하기 위하여 "Boolean real"을 활용하여 부분집합이 공집합인 Case를 걸러주었고, 이렇게 해서 답을 맞췄다.