✍ 순열이란?

• 순열은 서로 다른 n개의 원소 중에서 중복을 허용하지 않고 r개를 선택하여 나열하는 경우의 수. 조합과 달리, 순열은 순서를 고려한다는 게 중요
• nPm (1,2,3)과 (1,3,2)는 다름. 즉 element 값, 순서 다 중요
  • n P m = n! / (n− m)!
  • 6 P 3 = 6∗5∗4

👏 순열 특징

• 조합은 과거에 시작점으로 삼았던 원소는 다시 쳐다도 보지 않는다고 했다. 하지만, 순열은 과거에 시작점으로 삼았던 원소를 다시 쳐다봐야 함. 왜냐하면, 순열은 순서가 달라지면 다른 경우의 수로 취급하기 때문이다.

👏 소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;
//중복허용은 check함수를 제외하면 된다
int N;
vector<int> arr={1,2,3,4};
vector<int> visited;

bool check(int idx,int val) {
	for (int i = 0; i <= idx; i++) {
		if (visited[i] == val) {
			return false;
		}
	}
	return true;

}
void dfs(int idx) {

	if (idx == visited.size() - 1) {
		for (int i = 0; i < visited.size(); i++) {
			cout << visited[i] << ' ';

		}
		cout << '\n';
		return;
	}
	//idx==0
	//다음 idx=idx+1
	int next_idx = idx + 1;
	for (int i = 0; i < arr.size(); i++) {
		if (check(idx,arr[i]) == 1) {
			visited[next_idx] = arr[i]; //<--지금 쓰려는 이값이 쓰여있나??
			dfs(next_idx);
			visited[next_idx] = 0;
		}
	}
	
}

int main(void) {
	visited.resize(arr.size());


	//항상 선방문 후dfs
	for (int i = 0; i < arr.size(); i++) {
		visited[0] = arr[i];
		dfs(0);
		visited[0] = 0;
	}
	return 0;
}

✍ 조합이란?

• 조합은 서로 다른 n개의 원소 중에 중복을 허용하지 않고 r개를 뽑는 경우의 수를 말한다. 조합은 원소를 뽑기만 하고 그들의 순서는 고려하지 않는다.
• nCr (1,2,3)이나 (1,3,2)나 똑같음. 즉 element 값만 중요. 순서 (X)
  • n C r = n P r / r !
    6 C 3 = (6!/3!) /3! = 20

👏 조합 특징

• 조합은 과거에 시작점으로 삼았던 원소는 다시 쳐다도 보지 않는다.