kingsubin

import java.io.*;
import java.util.*;
 
public class boj_1182 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[] val;
    static int n, s, ans;
 
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
 
        val = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            val[i] = Integer.parseInt(st.nextToken());
        }
 
        func(0, 0);
        if (s == 0) ans--;
        System.out.println(ans);
    }
 
    static void func(int k, int sum) {
        if (k == n) {
            if (sum == s) ans++;
            return;
        }
 
        func(k + 1, sum);
        func(k + 1, sum + val[k]);
    }
}
 

 

- 백트래킹

 

- 원소가 n개인 집합에서 부분집합의 갯수는 2^n - 1개

- 현재의 원소를 더할지 더하지 않을지를 생각 

 

- C++의 경우 STL next_permutaton 사용가능, 자바로는 직접 구현해야함

 

 

---

import java.io.*;
import java.util.StringTokenizer;
 
// bitmask
public class boj_1182 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n, s, ans;
    static int[] a;
 
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
        a = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
 
        for (int i = 1; i < (1 << n); i++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
                if ( (i & (1 << j)) != 0) {
                    sum += a[j];
                }
            }
            if (sum == s) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

 

20.12.09 추가

- 비트마스크를 사용한 풀이 

 

 

 

 

---

www.acmicpc.net/problem/1182