[백준] 1182 부분수열의 합

📌 문제

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

✔ 접근방법

주어진 수열의 부분집합을 구하고, 그 부분집합의 합이 S와 같은지 확인하면 된다.
부분집합을 구하는 방법은 1.백트래킹 2.재귀함수 두가지를 이용해서 구할 수 있다.

현재 코드에선 재귀함수를 이용하여 작성하였다.

✔ 코드

import java.util.Scanner;

public class Main {

	static int result = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int s = sc.nextInt();
		int[] arr = new int[n];

		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		
		powerset(arr, n, 0, s, 0);
		
		//s가 0일경우 공집합인 순열의 조합때문에 +1이 되므로 값을 빼줌
		if(s == 0)
			result--;
		
		System.out.println(result);
	}

	private static void powerset(int[] arr, int n, int idx, int s, int sum) {
		
		if (idx == n) {
			if(sum == s)
				result++;
			return;
		}
		
		sum = sum+arr[idx];
		
		//값을 더한경우,
		powerset(arr,  n, idx + 1, s, sum-arr[idx]);
		//값을 더하지않은 경우
		powerset(arr,  n, idx + 1, s, sum);
	}
}

출처 : https://www.acmicpc.net/problem/1182