BOJ/1182

부분수열의 합

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

int count = 0;
int t, m;
int arr[22];
int arr2[22];

void dfs(int start, int depth, int hap) {
    if (depth == hap) {
        int sum = 0;
        for (int i = 0; i < hap; i++) {
            sum += arr2[i];
           // printf("%d ", arr2[i]);
        }
        //printf("\n");
        if (sum == m) {
            count++;
        }
        return;
    }
    else {
        for (int i = start; i < t; i++) {
            arr2[depth] = arr[i];
            dfs(i + 1, depth + 1, hap);
        }
    }
}



int main() {

    
    scanf("%d %d", &t, &m);

    for (int i = 0; i < t; i++) {
        scanf("%d", &arr[i]);
    }
    for (int i = 1; i <= t; i++) {
        dfs(0, 0, i);
    }
   

    printf("%d", count);

    return 0;
}​

이전 포스팅이였던 로또의 응용 문제이다. 똑같이 순열을 뽑아 판단하는 것이지만 이번엔 순열을 뽑는 개수가 고정된 것이 아니라 여러 경우가 있는 것 hap이라는 변수를 따로 설정해 주어 hap만큼 조합을 구성하는 것으로 하였다. 합이 1개~t개 까지 가능함으로 dfs를 t번 돌려준다.

count를 그냥 전역변수로 설정하고 조건이 일치 할 때마다 count++

순열을 구성하는 법/ 조합을 구성하는 법은 거의 외우다 싶이 하는 것이 도움이 될 것이라는 생각이 든다.