[문제풀이] B1182 부분수열의 합

부분수열의 합

---

  🪅 조건을 만족하는 모든 경우의 수를 구하는 문제에서 완전탐색을 생각할 수 있는가
  🪅 부분집합 알고리즘을 구현할 수 있는가
  🪅 flag를 이용해서 조건을 추가로 설정할 수 있는가

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;
    static int N;
    static int S;
    static int cnt;
    static boolean[] isSelected;
    public static void subset(int r) {
        // 종료조건
        if(r == N) {
            int sum = 0;
            boolean flag = false;
            for(int i = 0; i < N; i++) {
                if(isSelected[i]) {
                    sum += arr[i];
                    flag = true;
                }

            }
            // 조건만족
            if(sum == S && flag) {
                cnt++;
            }
            return;
        }

        isSelected[r] = false;
        subset(r+1);

        isSelected[r] = true;
        subset(r+1);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(token.nextToken());
        S = Integer.parseInt(token.nextToken());
        arr = new int[N];
        isSelected = new boolean[N];

        token = new StringTokenizer(br.readLine(), " ");
        // N개의 정수로 이루어지 수열
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(token.nextToken());
        }
        subset(0);
        System.out.println(cnt);
    }
}

💡 문제 접근 과정
배열의 어떤 각 요소를 포함하고 말고의 모든 경우의 수를 구해서 조건을 만족하는 경우를 세면 문제를 해결할 수 있다.
때문에 각 요소를 포함여부를 구하는 부분집합 알고리즘으로 구현하였다.
다만, 주의할 점은 S = 0일 때(만들어야하는 합이 0일 때), 요소를 하나도 포함하지 않아도 조건을 만족할 수 있으니,
요소를 하나라도 포함할 때만 flag = true로 만들어 이를 만족 조건으로 추가로 설정한다.