💡문제 분석 요약

• 주어진 배열에서 길이가 1 이상인 모든 부분수열 중, 그 합이 특정 값 S가 되는 경우의 수를 찾아야 한다.
  1. 배열 arr와 정수 S가 주어진다.
  2. 배열의 모든 부분수열 중 합이 S가 되는 경우의 수를 구해야 한다.

💡알고리즘 설계

• 부분수열 탐색 배열의 각 원소를 선택할지 말지를 결정해서 모든 부분수열을 탐색해야 한다. 총 경우의 수는 2^n이다.
• 백트래킹 배열의 원소를 하나씩 선택하거나 선택하지 않는 방식으로 재귀적으로 모든 경우의 수를 탐색할 수 있다. 이때, 부분수열의 합이 S와 같으면 카운트를 증가시킨다.
• 경우의 수 카운팅 모든 경우를 탐색하면서 합이 S인 부분수열을 카운트한다.
• 예외 처리 공집합은 제외하고 길이가 1 이상인 부분수열만 고려한다.

💡코드

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim().split('\\n');

const [n, S] = input[0].split(' ').map(Number);
const arr = input[1].split(' ').map(Number);

let count = 0;

function dfs(index, sum) {
  if (index === n) return;
  
  sum += arr[index];

  // 부분수열의 합이 S와 같은지 확인
  if (sum === S) count++;
  
  // 현재 원소를 포함하는 경우와 포함하지 않는 경우 모두 탐색
  dfs(index + 1, sum);  // 현재 원소를 포함한 경우
  dfs(index + 1, sum - arr[index]);  // 현재 원소를 포함하지 않은 경우
}

// 탐색 시작
dfs(0, 0);

console.log(count);

💡시간복잡도

• 배열의 길이 n에 대해 2^n개의 경우가 있으므로 시간 복잡도는 O(2^n)이다.
• n이 최대 20까지 가능하므로 2^20 = 1,048,576개의 경우의 수를 계산하는 것은 시간 내에 가능하다.