Q 1182 부분수열의 합

💡 문제 요약 및 분석

N 개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하자.

💡 알고리즘 설계

✅ 백트래킹 조건 : 현재 요소를 선택하거나, 선택하지 않거나 두 개의 선택지로 나뉜다.

1. 입력

   • 표준입력 : int N, int S
   • 표준입력 : int[] numbers

2. 연산

   • 인덱스 0, 합계 0 에서 시작한다.
   • 현재 인덱스를 선택하는 경우, 선택하지 않는 경우 두 가지를 재귀함수로 실행한다. 그림으로 그려보자면 트리 모양으로 모든 경우의 수를 탐색하게 된다.

3. 출력

   • result 변수를 출력한다.

💡 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int S;
    static int[] numbers;
    static int result;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer input = new StringTokenizer(br.readLine());
        N = Integer.parseInt(input.nextToken());
        S = Integer.parseInt(input.nextToken());
        input = new StringTokenizer(br.readLine());
        numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(input.nextToken());
        }
        br.close();

        backTracking(0, 0);
        if (S == 0) result--;
        System.out.println(result);
    }

    static void backTracking(int idx, int sum) {
        if (idx == N) {
            if (sum == S) result++;
            return;
        }

        // 현재 요소를 포함하는 경우
        backTracking(idx + 1, sum + numbers[idx]);

        // 현재 요소를 포함하지 않는 경우
        backTracking(idx + 1, sum);
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(n^2)	O(n)