조합
- n개의 숫자 중 r개의 수를 순서 없이 뽑는 경우
- 순열과의 차이점 : 순서가 중요하지 않다.
조합 구현 - 완전탐색
- 완전탐색으로 현재 인덱스를 선택하는 경우와 선택하지 않는 경우를 구현하면 된다.
백트래킹으로 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
// 호출시 combination(arr, visited, 0, n, r);
public static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
if (r == 0) {
print(arr, visited, n);
return;
}
for (int i = start; i < n; i++) {
visited[i] = true;
combination(arr, visited, i+1, n, r-1);
visited[i] = false;
}
}
start: 기준이 될 인덱스.start보다 작으면 뽑을 후보에서 제외된다.
파라미터 설명
arr: 조합을 뽑아낼 배열output: 조합에 뽑혔는지 체크하는 배열n: 배열의 길이r: 조합의 길이 -> 숫자를 하나 뽑을 때마다 r을 하나씩 줄여준다. r==0이 되면 r개의 숫자를 모두 뽑은 상태다.visited: 해당 인덱스를 뽑는다면 true가 되고, 뽑지 않는다면 false가 된다.
depth를 활용한 재귀로 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
if (r == 0) {
print(arr, visited, n);
return;
}
if (depth == n) return;
visited[depth] = true;
combination(arr, visited, depth + 1, n, r - 1);
visited[depth] = false;
combination(arr, visited, depth + 1, n, r);
}
