https://www.acmicpc.net/problem/16938

풀이

import java.io.*;
import java.util.*;

public class Main {
    static int N, L, R, X, ans;
    static int[] A;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        X = 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());
        }

        dfs(0,0,0,Integer.MIN_VALUE,Integer.MAX_VALUE);

        System.out.print(ans);
    }

    static void dfs(int idx, int cnt, int sum, int max, int min){
        if(idx == N){
            if(cnt < 2 || L > sum || R < sum || X > max - min){
                return;
            }
            ans++;
            return;
        }

        int nMax = Math.max(max, A[idx]);
        int nMin = Math.min(min, A[idx]);

        dfs(idx + 1, cnt + 1, sum + A[idx], nMax, nMin);

        dfs(idx + 1, cnt, sum, max, min);
    }
}

풀이

• 완전탐색 문제
• 조합
  boolean []visited 배열을 쓰지 않아도 풀이가 가능하다.
  각 원소를 선택했는지 여부를 따로 추적할 필요가 없기 때문!
  👉 visited 배열을 사용한 이유는 선택한 원소를 나중에 다시 선택하지 않기 위해서!!
  그러나 dfs 함수 내에서 선택한 경우와 선택하지 않은 경우를 각각 호출하여 중복을 피하고 있으므로, visited 배열을 사용할 필요가 없음