백준/1182/백트래킹/부분수열의 합

백준/1182/백트래킹/부분수열의 합
이번은 백트래킹을 이용한 조합 유형 문제입니다.

void permutation(int cur){
	if(cur==K){
    ...
    return;
    }
    for(int i=0;i<N;i++){
    	if(!isused[i]){
        	result[i]=i;
           	isused[i]=true;
            func(cur+1);
            isused[i]=false;
        }
    }
}

우선 위와같은 순열 함수를 하나 짜고 저기서 어떻게 변형 시켜야 조합 함수가 될 수 있을까 생각해보았습니다.
순열은 다른 배열과의 차이점을 순서로 나타내고 조합은 순서를 상관하지 않기 때문에 중복된 요소가 중복되는 배열은 나올 수 없는것에 중점을 두고 생각해보았습니다.

위와같이 순열로 배열을 만들 경우에는 처음 원소부터 검사하여 사용하는지 안하는지 유무를 검사합니다. 즉, 순서가 차이를 만들기 때문에 내가 현재 첫번째 순열로 둔 원소보다 낮은 인덱스값의 원소를 사용해도 되는것입니다.
반면에 조합같은 경우에 순서가 차이를 만들지 않기 때문에 순열에 넣은 원소보다 전의 원소를 넣으면 중복된 배열이 되어버립니다.

  for(int i=0;i<N;i++){
    	if(!isused[i]){
        	result[i]=i;
           	isused[i]=true;
            func(cur+1);
            isused[i]=false;
        }
    }

즉 이 반복문에서 처음 원소부터 검사하는게 아닌 내가 배열에 넣은 함수보다 인덱스가 높은 함수를 뽑아오게 하면 되는 것이었습니다.
cur 함수는 현재 몇번째 원소를 뽑는것인지 확인해야 하니 그대로 두고
새로운 변수로 반복문에 시작점을 다음 재귀함수에 넘겨줘야합니다.

void combination(int cur,int a){
	if(cur==K){
    ...
    return;
    }
    for(int i=a;i<N;i++){
    	if(!isused[i]){
        	result[i]=i;
           	isused[i]=true;
            func(cur+1,i+1);
            isused[i]=false;
        }
    }
}

위와같이 다음 원소에 i+1를 넘겨 그 원소를 시작 위치로 두게 만들어 combination 함수를 완성했습니다.

그럼 이제 문제를 풀기위한 준비는 끝났습니다.
부분 수열이라 함은 공집합을 시작으로 원소가 1개일때 2개일때...N개일때까지 여러개가 있습니다.
공집합은 애초에 원소가 존재하지 않으니 제외하고 1개~N개를 뽑기 위해서는

if(cur==k)

이부분이 중요합니다. 이 부분을 일반화 시키기 위해 combination 함수에 새로운 변수를 추가해주었습니다.

void combination(int cur,int a,int K){
	if(cur==K){
    ...
    return;
    }
    for(int i=a;i<N;i++){
    	if(!isused[i]){
        	result[i]=i;
           	isused[i]=true;
            func(cur+1,i+1);
            isused[i]=false;
        }
    }
}

K 부분은 5개의 배열에서 몇개를 뽑는지에 몇개를 담당합니다.
combination함수에 일반화가 끝났으니 이를 이용해

void func() {
	for (int i = 1; i <= N; i++) {
		combination(0, 0, i);
	}
	solution();
}

이런식으로 반복문을 만들어주어 해결하였습니다.

풀이

1. 첫번째풀이

#include<iostream>
#include<vector>
using namespace std;

int N, S;
int arr[20];
int isused[20];
int result[20];
int result_c;

void func();
void combination(int cur,int a,int K);
int sum(int K);
void solution();

void func() {
	for (int i = 1; i <= N; i++) {
		combination(0, 0, i);
	}
	solution();
}

void combination(int cur,int a,int K) {
	if (cur == K) {
		/*
		for (int i = 0; i < K; i++)
			cout << result[i] << ' ';
		cout << '\n';
		*/
		if (S == sum(K))
			result_c++;
		return;
	}
	for (int i = a; i < N; i++) {
		if (!isused[i]) {
			result[cur] = arr[i];
			isused[i] = true;
			combination(cur + 1,i+1,K);
			isused[i] = false;
		}
	}
}

int sum(int K) {
	int tmp=0;
	for (int i = 0; i < K; i++)
		tmp += result[i];
	return tmp;
}

void solution() {
	cout << result_c << endl;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N >> S;

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	func();
}