백트래킹(2) - 부분수열의 합, 등

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

1182번: 부분수열의 합

 

처음에는 답지를 보지 않고 어떻게든 혼자 풀려고 하다가 for문을 사용했다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,s,cnt;

int isused[21];
int arr[21];
int input[21];

void func(int k,int set){
	if(k==set){
		int sum=0; 
		for(int i=0;i<set;i++){
			//cout << input[arr[i]] << " ";
			sum+=input[arr[i]];
		}
		if(sum==s) cnt++;
		//cout << "\tcnt: " << cnt << "\n";
		return;
	}
	int st=0;
	if(k!=0) st=arr[k-1]+1;
	for(int i=st;i<n;i++){
		if(!isused[i]){
			isused[i] = true;
			arr[k] = i;
			func(k+1,set);
			isused[i] = false;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>s;
	for(int i=0;i<n;i++) cin>>input[i];
	sort(input,input+n);
	for(int i=1;i<=n;i++) func(0,i);
	cout << cnt;
    return 0;
}

백트래킹 문제는 N과 M만 풀어봐서 이런 식으로 밖에 구현하지 못했다.  그래서 풀이를 확인했는데 

// http://boj.kr/792d9af025724ce2912c77e8d56793d1
//https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0C/1182.cpp
#include <bits/stdc++.h>
using namespace std;

int n, s;
int arr[30];
int cnt = 0;
void func(int cur, int tot){
  if(cur == n){
    if(tot == s) cnt++;
    return;
  }
  func(cur+1, tot);
  func(cur+1, tot+arr[cur]);
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> s;
  for(int i = 0; i < n; i++)
    cin >> arr[i];
  func(0, 0);
  if(s == 0) cnt--;
  cout << cnt;
}

 

값을 더하거나 더하지 않는 경우로 구분해서 이런 알고리즘을 짤 수 있었다...

---

https://www.acmicpc.net/problem/6603

6603번: 로또

#include <bits/stdc++.h>
using namespace std;
int k=1;
int input[20];
int arr[20];
bool isused[20];
void func(int m){
	if(m==6){
		for(int i=0;i<6;i++) cout<<input[arr[i]]<<" ";
		cout<<"\n";
		return;
	}
	int st=0;
	if(m!=0) st=arr[m-1]+1;
	for(int i=st;i<k;i++){
		if(!isused[i]){
			isused[i]=true;
			arr[m]=i;
			func(m+1);
			isused[i]=false;
		}
	}
}

int main(){
	while(1){
		cin>>k;
		if(k==0) break;
		for(int i=0;i<k;i++) cin>>input[i];
		func(0);
		cout<<"\n";
	}
  return 0;
}

 

N과 M 형식의 간단한 문제였다.

---