(코테) 백준_1182_부분수열의 합 백트레킹

 

 

 

내가 제출한 답

 

package test;

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

public class testest {
    static int n, s, result = 0;
    static int[] list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
        
        list = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0, 0);

        // 공집합 제외
        if (s == 0) result--;

        System.out.println(result);
    }
    // n=5 , s =0 
    static void dfs(int index, int sum) {
        if (index == n) {
            if (sum == s) {
                result++;
            }
            return;
        }

        // 현재 원소를 선택하는 경우
        dfs(index + 1, sum + list[index]);

        // 현재 원소를 선택하지 않는 경우
        dfs(index + 1, sum);
    }
}

 

 

 

 

회고.

dfs()를 두번 사용하여 , 선택함 선택 안함을 구현하는게 참신했따.....

백트레킹이 처음에 가장 어려웠지만 점점 더 이해가 생기고 있는거 같다....

지치지말고 화이팅..!