1. 순열, 조합, 부분집합

게시에 들어가기에 앞서...

• 집합과 맵
  https://www.acmicpc.net/step/49
• 정수론과 조합론
  https://www.acmicpc.net/step/18
• n과 m
  https://www.acmicpc.net/search#q=n%EA%B3%BC%20m&c=Problems
• 누적합
  https://www.acmicpc.net/step/48

1. 순열(Permutation)
서로 다른 것 중 몇개를 뽑아서 한 줄로 나열하는 것
서로 다른 n개중 r개를 택하는 순열을 아래처럼 표현한다.

nPr

nPr은 다음과 같은 식이 성립한다.
nPr = n (n-1) (n-2) * ... (n - r + 1)
nPn = n!

코드로 표현하려면 ?

• nPr이라고 했을 때!
• 순열을 저장할 배열
• visit을 체크할 boolean 배열 : 인덱스에 해당하는 숫자가 사용중인지
• 재귀함수라면, 매개변수로 현재까지 뽑은 개수를 저장
• 핵심은 boolean으로 check해가면서 선택과 재귀 종료 후 선택 풀기를 반복해야 한다는 것

perm(int cnt) { // cnt : 현재까지 뽑은 개수
	if (cnt == r) return;
    for (int i = 1; i <= n; i++) {
    	if(visit[i]) continue;
        number[cnt] = i;
        visit[i] = true;
        perm(cnt + 1);
        visit[i] = false;
    }
}

1-2. 중복 순열
중복 순열의 경우, 이미 뽑은 수인지 체크할 필요가 없어진다. 코드로는 더 간결하다.

perm(int cnt) { // cnt : 현재까지 뽑은 개수
	if (cnt == r) return;
    for (int i = 1; i <= n; i++) {
        number[cnt] = i;
        perm(cnt + 1);
    }
}

2. 조합(Combination)
서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합이라고 부른다.
유추되는 시간복잡도를 따져야함
30C15 -> 대략 1억 5천 (1초 넘어감)

이미 뽑은 수의 다음 인덱스 부터 뽑으면 순서를 고려할 수 있다.

nCr

nCr은 다음과 같은 식이 성립한다.
nCr = n! / (n-r)!r! (n >= r)
nCr = n-1Cr-1 + n-1Cr // 재귀적 표현
nCr = n n-1 ... n-r + 1 / r!

코드로 표현하려면 ?

• nCr이라고 했을 때!
• 조합을 저장할 배열
• 재귀에 시작 값과, 뽑을 개수를 매개변수로 전달

comb(int cnt, int start) {
	if (cnt == r) return;
    for (int i = start; i <= n; i++) {
        number[cnt] = i;
        comb(cnt + 1, i + 1);
    }
}

1-2. 중복 조합
중복 조합의 경우, 자기 자신부터 시작하면 된다.

comb(int cnt, int start) {
	if (cnt == r) return;
    for (int i = start; i <= n; i++) {
        number[cnt] = i;
        comb(cnt + 1, i);
    }
}

3. 부분 집합(Sub-set)
부분집합은 조합으로도 풀 수 있다.
부분집합의 핵심은 선택함과 선택하지 않음의 반복에 있음

따라서 만들 부분집합의 크기와 같은 크기의 boolean배열을 만들고 t, f를 체크함 (뽑음과 뽑지 않음)

n까지의 부분집합?

subset(int i) { // 부분집합에 고려해야할 인덱스
	if(i == n) return;
    visit[i] = true;
    subset(i + 1);
    visit[i] = false;
    subset(i + 1);
}