완전탐색 문제에서 사용하는 조합 알고리즘
프로그래머스의 "메뉴 리뉴얼" 문제를 풀때 사용하였다.
재귀함수를 이용하여 구현할 수 있다.
함수를 재귀적으로 계속 호출하면서
현재 인덱스의 요소를 선택했을때와 선택하지않았을때로 계속 분기하고
원하는 갯수만큼 선택을 했을때는 함수호출을 종료시키는 방식으로 찾는다.
class Solution {
public String[] solution(String[] orders, int[] course) {
String[] str = {"a", "b", "c"};
boolean[] visited = new boolean[str.length]
// str 중 2개만 뽑는경우
combination(str, visited, 0, str.length, 2);
}
// 조합 알고리즘
public void combination(String[] str, boolean[] visited, int idx, int n, int r) {
// 조합을 찾았을때
if (r == 0) {
for (int i = 0; i < n; i++) {
if (visited[i]) {
System.out.print(str[i]);
}
}
return;
}
// 또 다른 리턴 조건
if (idx == n) {
return;
}
// 현재 인덱스의 숫자를 선택했을때
visited[idx] = true;
combination(str, visited, idx+1, n, r-1);
// 현재 인덱스의 숫자를 선택 안했을때
visited[idx] = false;
combination(str, visited, idx+1, n, r);
}