[BOJ] 1182 부분수열의 합

부분수열의 합

풀이

• 크기가 양수인 부분 수열 중에서, 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구해라.
• 1부터 N까지 조합의 모든 경우의 수를 구해서 S가 되면 answer++를 해줬다.

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    static int answer = 0;
    static int S;
    static int[] arr;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for(int size=1;size<=N;size++)
        {
            dfs(0,size,new boolean[N],0,0);
        }
        System.out.println(answer);
    }
    private static void dfs(int sum, int size,boolean[] visited, int depth,int start){
       if(depth==size){
           if(sum==S){
               answer++;
               return;
           }
       }
       for(int i=start;i<arr.length;i++){
           if(!visited[i]){
               visited[i] = true;
               dfs(sum+arr[i],size,visited,depth+1,i+1);
               visited[i] = false;
           }
       }
    }
}

• 풀이를 찾아보니까, 조합 말고 그냥 선택했을 때, 안했을 때를 더 쉽게 나타내는 방법이 있다.

public static void dfs(int index, int sum){
	if(index==N){
    	if(sum==target){
        	answer++;
        }
        return;
    }
    dfs(index+1,sum+arr[index]); 현재 원소를 선택했을 때
    dfs(index+1,sum);	현재원소를 선택 안했을 때
}