JavaScript - 조합 구하기 (재귀함수)

 

 

조합은 순서 상관없이 경우의 수를 구하는 것이다. 그림을 보면 한번에 이해가 될 것이다.

[1,2,3] 배열의 경우 [1,2], [2,3], [1,3] 이렇게 세가지 조합이 나온다

 

 

---

 

JavaScript - 조합 구하기 (재귀함수)

 

조합을 구하기 위해서는 재귀함수를 응용한다.

반복문으로 구할 수 있지만 일일이 구하고자 하는 숫자만큼 반복해주어야되어 코드가 길고 복잡해질 수 있기 때문이다.

// 1
function getCombination(arr, selectNum){
    const result = []; // 결과값을 담은 배열선언 
    if(selectNum === 1) { // selectNum 이 1 일 떄 (재귀함수의 종료조건, 탈출구!)
        return arr.map(item => [item])  // ex) [[2], [3]] 이런식으로 값이 리턴된다 
    }
    
    // 2
    arr.forEach((fixedNum, index, arr) => {
    	// 3 : 처음 하나(fixedNum)를 제외한 나머지를 배열로 만들기 ex) 1을 제외하면 [2, 3, 4]
        const rest = arr.slice(index - 1); 
        
        // 4 : selectNum === 1 이 되서 배열을 리턴하며 종료할 때까지 재귀된다
        const combination = getCombination(rest, selectNum - 1);
        
        // 5 : 앞에서 따로 뺴놓은 첫번째 수(fixedNum)를 각각 배열 값에 추가해주자
        const attached = combination.map(c => [fixedNum, ...c])
        
        // 6 : reuslt 배열에 push 해준다
        // (spread를 사용하는 이유는 반환된 배열들을 한 배열 안으로 넣기 위해서이다)
        reuslt.push(...attached);
    }) 
    
    // 7 : for문이 끝나면 배열을 반환하며 함수 종료!
    return result;
}

getCombination([1,2,3,4], 3);

 

 

 

재귀함수 실행과정

한마디로 내가 이해한 재귀함수는 인셉션과 같다

인셉션에서는 kick 으로 꿈에서 탈출하는 것처럼, 함수는 return을 해야 종료가 된다.

 

첫번째 함수(첫번째로 잠든 사람) > 두번째 함수(두번째로 잠든 사람) > 세번째 함수(세번째로 잠든사람) 이라고 가정해보자 

 

세번째 함수의 리턴 값으로 두번째 함수의 실행을 돕고,

(세번째로 잠든사람을 깨워 얻은 값으로 두번째로 잠든사람의 꿈을 깨는 단서로 사용해서)

 

두번째 함수의 리턴값으로, 첫번째 대왕함수의 리턴을 돕는 구조이다.

(두번째로 잠든사람의 꿈을 깨워 얻은 값으로 첫번째로 잠든 사람을 깨우고 값을 얻는 구조이다)

 

getCombination 함수는 selectNum === 1 이 되거나  for문을 다 돌아야 리턴문을 만날수 있다.

그럼 아래의 실행과정을 찬찬히 살펴보자

// getCombination( arr = [1, 2, 3, 4],  selectNum = 3 )
//  1. fixed: 1, index: 0, arr: [1, 2, 3, 4]		 ------------- 첫번째 for loop
//  2. rest: [2, 3, 4]
//  3. getCombination(arr = [2, 3, 4], selectNum = 2)
//    1) fixed: 2 index: 0 arr: [2, 3, 4]		 --- inner for loop1
//    2) rest: [3, 4]
//    3) getCombination(arr = [3, 4], selectNum = 1)
//      (1) selectNum === 1 return [[3], [4]]
//    4) combination = [[3], [4]];
//    5) attached = [[2,3], [2,4]];
//    6) result = [[2,3], [2,4]];

//    1) fixed: 3 index 1 arr: [2, 3, 4]		 	--- inner for loop2
//    2) rest: [4]
//    3) getCombination(arr = [4], selectNum = 1)
//      (1) selectNum === 1 return [[4]]
//    4) combination = [[4]]
//    5) attached = [[3,4]]
//    6) result = [[2,3], [2,4], [3,4]]

//    1) fixed: 4 index: 2 arr: [2, 3, 4]		 --- inner for loop3
//    2) rest: []
//    3) getCombination(arr= [], selectNum = 1)
//      (1) selectNum === 1 return []
//    4) combination = []
//    5) attached = []
//    6) result = [[2,3], [2,4], [3,4]]
//    7) return [[2,3], [2,4], [3,4]]
//  4. combination = [[2,3], [2,4], [3,4]];
//  5. attached = [[1,2,3], [1,2,4], [1,3,4]];
//  6. result = [[1,2,3], [1,2,4], [1,3,4]];

//  1. fixed: 2, index: 1, arr: [1, 2, 3, 4]		 ------------- 두번째 for loop
//  2. rest: [3, 4]
//  3. getCombination(arr = [3, 4], selectNum = 2)
//    1) fixed: 3 index: 0 arr: [3, 4]		  	--- inner for loop1
//    2) rest: [4]
//    3) getCombination(arr = [4], selectNum = 1)
//      (1) selectNum === 1 return [[4]]
//    4) combination = [[4]]
//    5) attached = [[3, 4]]
//    6) result = [[3, 4]]

//    1) fixed: 4 index 1 arr: [3, 4]		  	--- inner for loop2
//    2) rest: []
//    3) getCombination(arr = [], selectNum = 1)
//      (1) selectNum === 1 return []
//    4) combination = []
//    5) attached = []
//    6) result = [[3, 4]]
//    7) return [[3, 4]]
//  4. combination = [[3, 4]];
//  5. attached = [[2,3,4]]
//  6. result = [[1,2,3], [1,2,4], [1,3,4], [2,3,4]];

//  1. fixed: 3, index: 2, arr: [1, 2, 3, 4]		 ------------- 세번째 for loop
//  2. rest: [4]
//  3. getCombination(arr = [4], selectNum = 2)
//    1) fixed: 4 index: 0 arr: [4]			 --- inner for loop1
//    2) rest: []
//    3) getCombination(arr = [], selectNum = 1)
//      (1) selectNum === 1 return []
//    4) combination = []
//    5) attached = []
//    6) result = []
//  4. combination = []
//  5. attached = []
//  6. result = [[1,2,3], [1,2,4], [1,3,4], [2,3,4]];

//  1. fixed: 4, index: 3, arr: [1, 2, 3, 4]		 ------------- 네번째 for loop
//  2. rest: []
//  3. getCombination(arr = [], selectNum = 2)
//    1) 빈배열이라 실행 x
//  6. result = [[1,2,3], [1,2,4], [1,3,4], [2,3,4]];

//  7. return [[1,2,3], [1,2,4], [1,3,4], [2,3,4]];

 

 

 

공부를 하며 정리를 했어도 

여전히 재귀함수는 어렵다 그렇지만 이번기회를 통해 동작원리를 자세히 파헤쳐볼수있는 계기가 되었던 것 같다.

다음번에 다시 만나자! 그때는 반갑게 맞아줄테다