부분수열의 합

📍 문제 설명

 

💡 접근

부분수열의 합으로 사용한다/사용하지않는다. 로 풀 수 있는 문제

단, 모두 사용하지 않는 경우에는 합이 0이므로 s가 0일땐 하나 빼줘야한다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, s, answer;
    static int[][] board;
    static char[] c;
    static int[] arr,pm;
    static boolean[] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        n = kb.nextInt();
        s = kb.nextInt();
        arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }

        //합이 0일 때는 모두 포함하지 않는 경우는 제거
        if(s == 0) answer--;
        T.solution(0, 0);
        System.out.println(answer);
    }

    private void solution(int L, int sum) {
        //부분수열 완성
        if(L == n) if(sum == s) answer++;
        else {
            //숫자 더한다.
            solution(L+1, sum+arr[L]);
            //숫자 더하지 않는다.
            solution(L+1, sum);
        }
    }

}