백준[1182] 부분수열의 합

문제 풀이

문제 링크

http://icpc.me/1192

1192번: 장갑

풀이

백트레킹으로 조합을 만들면 된다.

만약 s가 0일때는 아무것도 뽑지 않는 경우가 생길 수 있기 때문에 정답에 -1을 해준다.

코드

#include <cstdio>

int n, s, ret;
int arr[22];
bool visited[22];

void solve(int cur, int sum) {
    if (sum == s) ret++;
    for (int i = cur; i < n; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        solve(i, sum + arr[i]);
        visited[i] = false;
    }
}

int main() {
    scanf("%d %d", &n, &s);
    for (int i = 0; i < n; i++) scanf("%d", arr + i);
    solve(0, 0);
    if (s == 0) ret--;
    printf("%d", ret);
}