[백준][1182번] 부분집합의 합

문제 URL

https://www.acmicpc.net/problem/1182 1) [비트마스크 풀이] 1) [재귀 풀이]

전체 풀이 (비트마스크) *

(1) 전체집합 = (1«N) - 1인 것을 이용해 모든 부분수열을 구할수 있다. (2) 계산된 부분수열 i를 활용해 모든 값을 더해서 구하고자 하는 값과 같은지 계산

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int ans = 0;
        //(1)
        for (int i = 1; i < (1 << n); i++) {
            int sum = 0;
            //(2)
            for (int k = 0; k < n; k++) {
                if ((i & (1 << k)) != 0) {
                    sum += a[k];
                }
            }
            if (sum == s) {
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}

전체 풀이 (재귀)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[] a;
    static int answer = 0;

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        go(0, 0,0, n, s);
        System.out.println(answer);
    }

    public static void go(int idx, int selected, int sum, int n, int s) {
        if (idx == n) {
            if (sum == s && selected != 0) {
                answer++;
            }
            return;
        }

        go(idx + 1, selected+1, sum + a[idx], n, s);
        go(idx + 1, selected, sum, n, s);
    }
}

```