[1,2,3,4]로 3개를 뽑는 조합을 만드는 방법을 생각해보면,
1을 선택하고 나머지 [2,3,4]중에서 2개를 뽑는 조합을 구한다
-> [2,3],[2,4],[3,4] 임. 여기에 1을 붙여준다.
[1,2,3],[1,2,4],[1,3,4]
2를 선택하고 나머지 [3,4]중에서 2개뽑는 조합을 구한다.
-> [3,4]임 여기에 2을 붙인다.
[2,3,4]
3을 선택하고 나머지 [4]중에서 2개뽑는 조합을 구한다.
->[]
4을 선택하고 나머지 []중에서 2개뽑는 조합을 구한다.
->[]
종료
[1,2,3],[1,2,4],[1,3,4],[2,3,4] :4가지
배열([1,2,3,4])을 순회하면서 하나씩 고정시키고 그 뒤에있는 나머지 원소들가지고 다시 재귀적으로 조합을 구해서 붙이면 된다.
재귀함수는 종료조건이 중요하다! 종료 조건이 없다면 무한루프처럼 스택이 계속 쌓여서 콜스택이 터지기 때문!
재귀 종료 조건: 하나를 선택할 때에는, 모든 배열의 원소를 선택해서 리턴한다
const getCombinations=(arr,selectNumber)=>{
//arr은 조합을 구할 배열, selectNumber: 몇개를 뽑아서 조합을 구할건지
const result=[];
if(selectNumber===1){
// 1개의 원소를 선택할때는 ex) A,B,C,D중 한개 선택
// [[A],[B],[C],[D]] 경우 밖에 없음
return arr.map((a)=>[a]);
}
arr.forEach((fixed,index,origin)=>{
const rest=origin.slice(index+1);//현재 인덱스 뒤에것부터 원본 배열의 끝까지 잘라서 나머지 배열을 만듬
const combinations=getCombinations(rest,selectNumber-1); //나머지배열에 대해서 조합을 구한다
const attached=combinations.map((el)=>[fixed,...el]);
//나머지배열에대해서 구한 조합에, 고정할 원소 하나를 맨 앞에 넣어준다
result.push(...attached)
});
return results;
조합으로부터 도출해낼 수 있다.
const getPermutations= (arr, selectNumber)=> {
const results = [];
if (selectNumber === 1) return arr.map((a) => [a]); // 1개씩 택할 때, 바로 모든 배열의 원소 return
arr.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index+1)] // 해당하는 fixed를 제외한 나머지 배열
const permutations = getPermutations(rest, selectNumber - 1); // 나머지에 대해 순열을 구한다.
const attached = permutations.map((permutation) => [fixed, ...permutation]); // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
results.push(...attached); // 배열 spread syntax 로 모두다 push
});
return results; // 결과 담긴 results return
};