개요

[링크]백준 1182번: 부분수열의 합

수열과 타겟값을 입력값으로 주고
해당 수열의 부분 수열의 합이
타겟값이 되는 경우의 수를 찾아라.

접근 방식

부분집합의 합이므로
연속된 순열의 합이 아닌 것에 주목을 해야하고
중복된 값도 허용한다.

• 백트래킹 방식으로 접근을 하였다.
  모든 경우에서의 부분 수열의 합을 체크해서
  값이 나오게 재귀함수를 짰다.

void solution(int startIdx,int amount,int target,int sum) {	//시작 인덱스, 배열안의 갯수,부분수열의 합, 지금까지의 합 
	if (sum == target && startIdx!=0) {	//startIdx가 0이면 안됨 맨처음 sum에 0을 넣어주므로 바로 답나옴
		ans++;							//여기서 return 해버리면 혹시 뒤에 답있을때 거름
	}
	else if (startIdx >= amount) return;

	for (int i = startIdx; i < amount; i++) {
		if (check[i]==false ) {
			check[i] = true;
			sum+=arr[i];
			solution(startIdx + 1, amount, target, sum);
			check[i] = false;
			sum -= arr[i];
			

		}
	}


}

하지만 계속 중복된 값이 나왔고,
또 헤매고 여기저기 찾고,
다른 구현들을 보면서 비교해 본 결과

solution재귀함수 부분에서 내가 원한건
매개변수로 넘어온 startidx 다음 값부터
조사하는 것이였는데,

저렇게 startIdx+1을 넣어주면 이전의 값도
다 포함하게 되버린다.
따라서 startIdx+1이 아니라 i+1을 넣어줘야
제대로 작동을 한다.

코드

#include<iostream>
using namespace std;

int arr[21] = { 0, };									//입력값으로 주는 수열
bool check[21] = {false,};								//방문했는지 체크하는 bool형함수
int ans = 0;											//답
void input(int& amount,int& target) {					//입력값 받는 함수
	int temp = 0;
	cin >> amount >> target;
	for (int i = 0; i < amount; i++) {
		cin >> temp;
		arr[i]=(temp);

	}
}
void solution(int startIdx,int amount,int target,int sum) {	//(시작 인덱스, 배열안의 갯수,부분수열의 합, 지금까지의 합)

	if (sum == target && startIdx!=0) {						//startIdx가 0이면 안됨. 맨처음 sum에 0을 넣어주므로 
															//target이 0이면 바로 답나옴
		ans++;												//여기서 return 해버리면 혹시 뒤에 답있어도 거름
	}
	else if (startIdx >= amount) return;					//return 조건

	for (int i = startIdx; i < amount; i++) {				//startIdx부터 amount까지
		if (check[i]==false ) {								//만약 방문안한 원소라면
			check[i] = true;								//방문 표기
			sum+=arr[i];									//지금까지의 합에 더해주고
			solution(i + 1, amount, target, sum);			//지금 인덱스의 +1부터 조사
			check[i] = false;								//빠져나왔으므로 false로 바꿔야 다음 재귀때 다시 들어감
			sum -= arr[i];									//마찬가지로 빠져나왔으므로 합에서 빼져야 함.
			

		}
	}


}
void print() {
	cout << ans;
}
int main()
{
	int amount = 0, target=0;
	input(amount,target);
	solution(0, amount, target, 0);
	print();
}

다른 방식

재귀함수를 호출하여 푸는 방식이다.
모든 값을 넣거나 안 넣거나에서 분기를 생성해서
총 시간복잡도 O(2^n)으로 푸는 방법이다.

코드

#include<iostream>
using namespace std;
int amount,target,ans=0;
int arr[20];
void input(){						//입력값 받는함수
	
	cin>>amount>>target;
    for(int i=0;i<amount;i++){
    	cin>>arr[i];
    }
}

void solution(int idx, int sum){	//재귀함수
	if(idx==amount) return;			//종료조건
    if(sum+arr[idx]==target ) ans++;//만약 조건에 맞으면 답 ++ 
    								//but 위와 마찬가지로 답 찾았다고 return하면 안됨.
                                    //여기선 idx!=0 조건 안넣어도 되는 이유는 
                                    //sum에 arr[idx]를 더해서 비교하므로 sum이 0일때 대비 안해됨.
    
    
    solution(idx+1,sum+arr[idx]);	//arr을 더했을때의 재귀
    solution(idx+1,sum);			//안 더했을때 재귀
}
void print(){
	cout<<ans;
}
int main(){
	input();	
	solution(0,0);
    print();
}

문풀후생

비록 startidx+1같은 사소한 실수를 해서
시간을 많이 쓰긴 했으나
수 많은 디버깅을 통해 좀 더 재귀함수의 원리에 대해
가까워진 느낌이다.
재귀함수, dfs에 대해 좀 더 익숙해지는 기회였다.