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);
}
}