[BOJ] 1182번 부분수열의 합

개요

N개의 정수로 이루어진 수열이 있을 때 부분수열의 합이 입력 S와 같은 경우의 수를 구하는 문제

부분수열을 구하는 코드 혹은 조합을 구하는 코드와 공집합일 경우를 확인하는 코드가 필요하다.

문제링크

코드

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

public class Baekjoon1182 {
    public static int n;
    public static int s;
    public static int[] arr;    //입력받은 숫자 저장
    public static boolean[] checked;
    public static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        
        for(int i=0;i<n;i++) 
            arr[i] = Integer.parseInt(st.nextToken());
        
        checked = new boolean[n];
        powerSet(0, 0);
        
        bw.write(count+"");
        bw.flush();
    }

    public static void powerSet(int k, int sumResult) {
        if(k == n) {   
            if(sumResult == s && isNotNullSet()) {  
            //부분집합의 합이 S와 같고 공집합이 아닐 경우
                count++;
            }
        }
        else {
            checked[k] = false; //k번째 정수가 포함되지 않을 때
            powerSet(k+1,sumResult);

            checked[k] = true;  //k번째 정수가 포함될 때
            sumResult += arr[k];
            powerSet(k+1,sumResult);
        }
    }

    public static boolean isNotNullSet() {  //공집합 유무를 확인
        for(int i=0;i<n;i++) {
            if(checked[i]) 
                return true;
        }
        return false;
    }
}

해결 과정

N과 M(1)의 순열 구하는 방식을 참고해서 조합을 구해 사용하려 했으나 잘 안 풀려서 부분집합을 구하는 방법을 인터넷에서 참고했다.

https://bcp0109.tistory.com/entry/부분집합-PowerSet-Java

부분집합에 수가 포함될 때마다 sumResult변수에 그 값을 더해주고 재귀로 넘겨주는 방식을 취했다.

이것만으로는 하나의 예외사항이 발생할 수 있었는데 바로 S의 값이 0일 때이다.

아무것도 선택되지 않음 공집할 일 때 s가 0이면 카운트가 올라가기 때문에 isNotNullSet()함수를 통해서 공집합인지 확인해주었다.

결과