DFS 순열 조합

순열

#include <vector>
#include <algorithm>

sort(v.begin(), v.end());
do {
	for(int i=0; i<v.size(); i++)
		// do smt

}while (next_permutation(v.begin(), v.end()));

-----------------------------
#include <iostream>
#include <vector>

using namespace std;

// 순열
// 123 ==  213 

int Arr[10] = {0,1,2,3,4,5,6,7,8,9};
bool Select[10];
vector <int> v;
int answer;

void DFS(int Cnt, int target_num)
{
    if (Cnt == target_num)
    {
        answer += 1;
        for (int i=0; i<v.size(); i++) 
            printf("%d ", v[i]);
        printf("\n");
        return;
    }
 
    for (int i = 0; i < 10; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        v.push_back(Arr[i]);
        DFS(Cnt + 1, target_num);
        Select[i] = false;
        v.pop_back();
    }
}

int main(void)
{

    int target_num;
    scanf("%d", &target_num);

    DFS(0, target_num);

    printf("answer: %d\n", answer);
}

조합

#include <iostream>
#include <vector>

using namespace std;

// 조합
// 123 !=  213 

int Arr[10] = {0,1,2,3,4,5,6,7,8,9};
bool Select[10];


void DFS(int Idx, int Cnt, int target_num)
{
    if (Cnt == target_num)
    {
        for (int i=0; i<10; i++) 
            if (Select[i])
                printf("%d ", Arr[i]);
        printf("\n");
        return;
    }
 
    for (int i = Idx; i < 10; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;

        DFS(i, Cnt + 1, target_num);
        Select[i] = false;
    }
}

int main(void)
{

    int target_num;
    scanf("%d", &target_num);

    DFS(0, 0, target_num);
}​

DFS_(순열_조합).pdf

0.09MB

 

 

중복조합

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <char> v = {'I', 'V', 'X', 'L'};
vector<int> res;
int n;

// 중복 조합
// 4개(v)에서 n 개 뽑기

void combination2(vector <char> comb, int idx, int cnt) {
	if(cnt == n) {
		int sum = 0;
		for(int i=0; i<n; i++) {
			//printf("%c", comb[i]);
			if(comb[i] == 'I')
				sum += 1;
			if(comb[i] == 'V')
				sum += 5;
			if (comb[i] == 'X')
				sum += 10;
			if(comb[i] == 'L')
				sum += 50;
		}
		res.push_back(sum);
		//printf("\n");
		return;
	}
	for(int i=idx; i<v.size(); i++) {
		comb[cnt] = v[i];
		combination2(comb, i, cnt+1);
	}
}


int main() {

	scanf("%d", &n);

	vector <char> comb(n);
	combination2(comb, 0, 0);

	sort(res.begin(), res.end());
	res.erase(unique(res.begin(), res.end()), res.end());

	printf("%lu\n", res.size());

	return 0;
}

 

조합은 전의 요소는 다시는 쳐다도 안본다는 것이 중요