조합 - 백준2798 블랙잭

이 문제는 순조부에서 조합에 해당한다.
주어진 n개의 숫자 중 m개를 선택하는 모든 경우의 수를 찾아보아야 한다.

조합 문제는 부분집합 문제와 상당히 유사한 것 같다.
가장 하단에 첨부한 순조부 문제 풀이에 대한 글을 보면 어떻게 유사한 지 알 수 있다.

설명은 다음 코드 주석을 참고

import java.io.*;
import java.util.*;
public class Main{
    static int n;
    static int[] ns;
    static int m;
    static int ans = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //n개 중 3개 골라서, m에 블랙잭
        //n개중 3개 고르는 경우의 수
        //한 번 고른거는 다시 못 고름
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        ns = new int[n];
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            ns[i] = Integer.parseInt(st.nextToken());
        }
        dfs(0, 0, 0);
        System.out.println(ans);
    }
    static void dfs(int idx, int selected, int sum){
    	//argument : 현재 깊이, 뽑은 갯수, (조건검사에 필요한)뽑은 숫자들의 합
    	//3개를 뽑았다면 검사
        if(selected == 3){
            if(sum <= m && sum > ans){
                ans = sum;
            }
            return;
        }
        //(dfs깊이가) n개까지 모두 탐색했다면 리턴
        if(idx == n){
            return;
        }
        //현재 원소를 뽑고 다음 원소 탐색
        dfs(idx+1, selected+1, sum+ns[idx]);
        //현재 원소를 뽑지 않고 다음 원소 탐색
        dfs(idx+1, selected, sum);
    }
}

순조부(순열, 조합, 부분집합)에 대한 설명은 아래 글 참고
알고리즘 - 순조부 문제(feat.백트래킹, 브루트포스)