DFS 기본 - 순열과 조합

📝 N과 M 순열

문제 링크 : https://www.acmicpc.net/problem/15649

vector<int> answer;
int used[10];

void nPm(int n, int m, int depth)
{
	if (depth >= m)
	{
		for (int i = 0; i < size(answer); i++)
			cout << answer[i] << " ";
		cout << endl;
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (used[i] == 1) continue;
		answer.push_back(i);
		used[i] = 1;
		nPm(n, m, depth + 1);
		answer.pop_back();
		used[i] = 0;
	}
}

📝 N과 M 조합

문제 링크 : https://www.acmicpc.net/problem/15650

일반적이지 않은 풀이 (수정)

vector<int> answer;
int used[10];

void nCm(int n, int m, int depth)
{
	if (depth >= m)
	{
		for (int i = 0; i < size(answer); i++)
			cout << answer[i] << " ";
		cout << endl;
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (used[i] == 1) continue;
		if (answer.size() != 0 && answer.back() > i) continue;
		answer.push_back(i);
		used[i] = 1;
		nCm(n, m, depth + 1);
		answer.pop_back();
		used[i] = 0;
	}
}

조합 수정

vector<int> answer;
int used[10];

void nCm(int n, int m, int depth, int start) 
{
	if(depth >= m)
    {
    	for(int i = 0 ; i < size(answer) ; i++) 
        	cout << answer[i] << " ";
        cout <<endl;
    	return;
    }
    
    for(int i = start, i <= n ; i++) 
    {
    	if(used[i] == 1) continue;
    	used[i] = 1;
    	answer.push_back(i);
        nCm(n, m, depth + 1, i + 1);
        used[i] = 0;
        answer.pop_back();
    }
}

📝 N과 M 중복순열

문제 링크 : https://www.acmicpc.net/problem/15651

vector<int> answer;
int used[10];
  
void nPim(int n, int m, int depth)
{
	if (depth >= m)
	{
		for (int i = 0; i < size(answer); i++)
			cout << answer[i] << " ";
		cout << endl;
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		answer.push_back(i);
		nPim(n, m, depth + 1);
		answer.pop_back();
	}
}

📝 N과 M 중복조합

문제 링크 : https://www.acmicpc.net/problem/15651

vector<int> answer;

void nHm(int n, int m, int depth)
{
	if (depth >= m)
	{
		for (int i = 0; i < size(answer); i++)
			cout << answer[i] << " ";
		cout << endl;
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		 if (answer.size() != 0 && answer.back() > i) continue;
		answer.push_back(i);
		nHm(n, m, depth + 1);
		answer.pop_back();
	}
}

😊 memo

📌ref

https://bloodstrawberry.tistory.com/57