[BOJ - JAVA] 1182 - 부분수열의 합(백트래킹)

# 주소

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.Scanner;
 
public class Main {
    static int n,sum, count=0;
    static int[] arr;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n= sanc.nextInt();
        sum= scan.nextInt();
        arr = new int[n];
        for (int i = 0; i <n ; i++) {
            arr[i] =  scan.nextInt();
        }
 
        dfs(0,0);
 
        if(sum==0){
            count--;
            System.out.println(count);
        }else {
            System.out.println(count);
        }
 
 
    }
 
    private static void dfs(int start , int i ){
        if(start==n){
            if(i == sum){
                count++;
            }
            return;
        }
        dfs(start+1, i+arr[start]);
        dfs(start+1, i); 
    }
}

간단했습니다. 

i + arr[start]한 값이 sum과 같아질때마다 count를 1씩 증가시킵니다. 

그리고 start의 개수는 n과 같아질 때만 적용이 되는 문제입니다.

또한 밑에 dfs를 2줄을 썼는데 이것은, start를 +1씩 해주면서 값을 증가시킬 수도, 아닐 수도 있을 때를 

다 포함시키기 위해서입니다. 결과적으로 모든 경우의 수를 가지므로 부분수열의 합은 백트래킹 방식으로

구현하면 되겠습니다.