알고리즘 문제를 풀다가 조합을 구해야할 상황이 있었다.
간단하게 중첩 반복문을 사용하면 쉽게 조합을 구할 수 있었지만, 이 방법에는 큰 제한 사항이 있었다.
n C r 에서 r 이 가변적이라면 반복문의 중첩 횟수가 달라져야 하기 때문에 , 이에 대해서는 중첩 반복문으로 조합을 구현하는 것은 제한된다.
그래서 가변적인 r에 대해서도 일관성 있게 조합을 구현할 수 있는 방법 중 , 백트래킹을 사용해 보았다.
백트래킹이란?
백트래킹(backtracking) : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다.
이번에 처음으로 백트래킹이라는 것을 접해보았는데, 그림을 보니 쉽게 이해할 수 있었다.
조합을 구하는 과정에서, r은 트리의 레벨이 될 것이고, 해당 레벨(r)에 도달한다면 다시 되돌아가서 다른 노드들에 대해서도 반복해서 해당 레벨까지 탐색을 하면 되는 방식이다.
A, B, C, D, E 중에 순서에 상관 없이 3가지를 뽑는 경우의수 ( 5C3 )
결과 : ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE
public class Combination{
public static void main(String[] args){
char[] arr = new char[]{'A','B','C','D','E'};
boolean[] visited = new boolean[arr.length];
comb_backtracking(0, 3, visited, arr); // 5C3
}
private static void comb_backtracking(int start, int r, boolean[] visited, char[] arr){
int n = arr.length;
if(r == 0){
print(visited, arr);
}
for(int i=start; i<n; i++){
visited[i] = true;
comb_backtracking(i+1, r-1, visited, arr);
visited[i] = false;
}
}
private static void print(boolean[] visited, char[] arr){
for(int i=0; i< visited.length; i++){
if(visited[i]){
System.out.print(arr[i]);
}
}
System.out.print(" ");
}
}
실행 결과
