조합
조합은 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다. 예시로 [1,2,3] 배열에서 2개를 선택해 만든 조합은 아래와 같다.
[1,2]
[1,3]
[2,3]조합 알고리즘
조합 알고리즘 설명은 해당 사이트를 참고하였다.
조합은 기호 nCr로 나타내며 nCr = n-1Cr-1 + n-1Cr이라는 성질을 가지고 있다. 즉 조합은 하나의 원소를 선택할 경우 + 하나의 원소를 선택하지 않을 경우 이 둘의 합을 나타낸다.
예를 들어 배열 (1,2,3) 중에서 2개를 뽑는 조합을 구한다고 생각해보자.
- (1, X) - 1을 뽑는 경우(하나의 원소를 선택할 경우)
- 2개 중 하나는 뽑혔으므로 남은 원소 2가지 중 하나를 선택하면 된다(2C1).
- 총 2개의 경우 (1,2) (1,3) -> 2C1
- (X, X) - 1을 뽑지 않은 경우(하나의 원소를 선택하지 않은 경우)
- 1은 이미 뽑혔으므로 남은 원소 2가지 중 2개를 선택하면 된다(2C2).
- 총 1개의 경우 (2,3) -> 2C2
이처럼 2가지로 나뉠 수 있다.
즉 (1,2,3)에서 2개를 뽑는 조합은 두 가지 경우를 합해 (1,2), (1,3), (2,3) 총 3가지가 된다.
백트래킹을 이용해 구현
1. 로직 설명
배열 [1,2,3] 중 2개의 원소를 뽑아 조합을 만들어보자.
먼저 조합을 저장할 빈 배열을 크기 2만큼 생성한다. 배열 위에 있는 별은 현재 상태에 위치하는지를 나타낸다.
조합의 맨 처음 원소를 배열의 첫 번째 원소인 1로 설정한다.
조합의 두 번째 원소로 들어갈 수 있는 원소는 2와 3이다. 먼저 2로 채워넣어보자.
현재 상태에서 조합이 완성되었으므로([1,2]) 이전 상태로 돌아간다.
조합의 두 번째 원소로 들어갈 수 있는 원소는 3이다. 따라서 3을 채워넣는다.
현재 상태에서 조합이 완성되었으므로([1,3]) 이전 상태로 돌아간다.
첫 번째 원소가 1인 조합은 더 이상 만들 수 없으므로 이전 상태로 돌아간다.
조합의 첫 번째 원소로 들어갈 수 있는 원소는 2이다. 따라서 2를 채워넣는다.
조합의 두 번째 원소로 들어갈 수 있는 원소는 3이다. 따라서 3을 채워넣는다.
현재 상태에서 조합이 완성되었으므로([2,3]) 이전 상태로 돌아간다.
현재 상태에서 두 번째 원소로 들어갈 수 있는 원소가 더 이상 없다. 따라서 이전 상태로 돌아간다.
현재 상태에서 첫 번째 원소로 3이 들어올 수 있다. 하지만 두 번째 원소로 들어갈 수 있는 원소가 더 이상 없으므로 백트래킹은 종료된다.
따라서 배열 [1,2,3]에 대해 2개의 원소를 뽑아 만들 수 있는 배열은 [1,2], [1,3], [2,3] 총 3가지이다.
2. 백트래킹 코드
-
배열 [1,2,3] 중 2개의 원소를 뽑아 조합을 만들어보자.
아래 코드에서 arr는 [1,2,3], k는 2이다. -
조합을 저장할 변수 comb의 각 원소의 값을 0으로 초기화해준다. 백트래킹을 진행하면서 각 idx의 값을 업데이트 시켜줄 것이다.
-
초기화한 comb에 대해 백트래킹을 진행하자. start는 사용할 수 있는 idx 범위를 나타내준다. start를 기준으로 for loop를 돌리면서 각 원소 값을 업데이트 시킨 다음 백트래킹을 진행하자.
-
만약 idx가 k와 같아진다면 조합을 완성한 것이다. 예컨대 조합 [1,2]를 만든 것이다. 따라서 해당 조합을 answer에 push하고 리턴해준다. 리턴을 하게 되면 이전 상태로 돌아가게 된다.
-
백트래킹이 전부 종료되면 answer에 원소를 두개 뽑아 만든 조합 [1,2], [1,3], [2,3]이 들어가 있다.
var combine = function(arr, k) {
const answer = [];
const comb = [...Array(k)].fill(0);
backTracking(answer, comb, arr, k, 0, 0);
return answer;
};
function backTracking(answer, comb, arr, k, idx, start) {
if (idx === k) {
return answer.push([...comb]);
}
for (let i=start; i<arr.length; i++) {
comb[idx] = arr[i];
backTracking(answer, comb, arr, k, idx+1, i+1);
}
}
// [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]
console.log(combine([1,2,3], 2));(ref) 조합 알고리즘 설명
