백준 1182 부분수열의 합

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

---

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int count=0;

    public static void subsequence(int[] sequence, int start, int sum, int s){
        sum+=sequence[start];
        if(sum==s)
            count++;

        for(int i=start+1; i<sequence.length; i++)
            subsequence(sequence, i, sum, s);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s=br.readLine();
        StringTokenizer st=new StringTokenizer(s);
        int n=Integer.parseInt(st.nextToken());
        int sum=Integer.parseInt(st.nextToken());
        s=br.readLine();
        st=new StringTokenizer(s);
        int[] sequence=new int[n];
        for(int i=0; i<sequence.length; i++)
            sequence[i]=Integer.parseInt(st.nextToken());

        for(int i=0; i<sequence.length; i++)
            subsequence(sequence, i, 0, sum);

        System.out.println(count);
    }
}

---

해결 과정

1. 크기가 1개인 부분 수열부터 크기가 N인 부분 수열까지 모두 탐색해서 그 요소의 합이 S와 같은 지 확인해야 한다고 생각했다. 친구가 현재의 인덱스를 포함하는 재귀 호출+포함하지 않는 재귀 호출의 방식으로 재귀적으로 문제를 푼 것을 봤고, 그것과 다른 풀이를 생각하기 위해서 노력했다.
   • 배열의 요소들을 각각 S와 비교해서 같은 지 검사하고, 배열의 요소 중 2개를 더할 수 있는 모든 경우의 수로 재귀 호출 해줬다. 예를 들어 처음 함수의 인자로 들어간 배열이 {1, 2, 3, 4, 5} 였다면 그 다음 인자로 들어가는 배열은 {3, 3, 4, 5}, {4, 2, 4, 5}, {5, 2, 3, 5}, ..., {1, 2, 3, 9} 이런 식이다. 하지만 만약 S가 7이라고 했을 때, {1, 2, 7, 5}, {3, 7, 5}, {7, 8} 모두 count가 들어가기 때문에 실패했다.
   • DFS 구현: start 변수보다 큰 인덱스를 sum에 추가하면서 재귀호출을 해줬다. 중복되는 경우도 생기지 않고 모든 탐색이 가능하다. start는 인덱스 0부터 배열의 마지막 인덱스까지 모두 호출해줘야 한다.
2. 😁