백준-1182번/부분수열의 합(java)

 

 

문제 이해

 

주어진 수열의 부분수열의 합이 S가 되는 경우의 수를 구해주면 되는 문제이다.

모든 경우의 수를 집고 넘어가야 하므로 dfs를 이용하면 쉽게 풀 수 있다.

 

문제 풀이

 

<dfs 함수>

private static void dfs(int start, int sum){
    if(start==N) {
        if (sum == S) {
            count++;
        }
        return;
    }

    dfs(start+1,sum+num[start]);
    dfs(start+1,sum);
}

 

 

배열에서 선택된 수를 더할지 아니면 그냥 넘어갈지를 결정하기 위해서 재귀 호출을 이용하였다.

 

그리고 start변수가 N이 되면 배열의 끝까지 도달한 경우인데 이때의 sum이 S와 같으면 경우의 수에 추가해준다.

 

집고 넘어가야 할 점

만약 S가 0이면 수열에서 아무것도 선택되지 않은 경우도 경우의 수에 추가가 된다. 이를 방지 하기 위해서 S가 0일때는 경우의 수에서 1을 빼준다.

if(S==0){
    count--;
}

 

 

<전체 코드>

import java.util.Scanner;

public class Problem1182 {
    static int  N;
    static int S;
    static boolean[] visit;
    static int[] num;
    static int count=0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N=scanner.nextInt();
        S=scanner.nextInt();
        visit=new boolean[N];
        num=new int[N];

        for(int i=0; i<N; i++){
            num[i]=scanner.nextInt();
        }

        dfs(0,0);

        if(S==0){
            count--;
        }
        System.out.println(count);
    }
    private static void dfs(int start, int sum){
        if(start==N) {
            if (sum == S) {
                count++;
            }
            return;
        }

        dfs(start+1,sum+num[start]);
        dfs(start+1,sum);
    }
}