77. Combinations javascript leetcode

문제링크

https://leetcode.com/problems/combinations/

Combinations - LeetCode

문제정보

간단하게 문제를 설명하자면 이렇습니다.

정수 n,k가 매개변수로 주어지고 조합을 구현해야합니다.

 

각 배열요소는 k만큼의 길이를 가지며.

1부터 n까지의 조합을 반환해야합니다.

 

k만큼의 길이가 주어지는데 k가 정해진값이 아니니

단순 for문 중첩으로 풀기는 꽤 힘들 것 같습니다.

 

따라서 재귀적인 솔루션을 활용하는게 좋을 것 같네요 역시 재귀는 아직 활용을 못해서

다른 사람의 풀이를 참고했습니다.

 

 

 

풀이 방법

 

var combine = function (n, k) {
    const output = []; // 2차원배열 리턴을 위한 output 변수에 빈 배열 선언
  
    const backtracking = (current, startNumber, k) => {
      // 재귀 선언 , 꼬리재귀형태구현 / i값을 for문 외부에서도 사용하기위해 startNumber선언
      if (n - startNumber + 1 < k) return; // 백트래킹을 위한 종료코드인듯한데 정확한 구동원리 모르겠음
      if (k === 0) return output.push(current); // 꼬리재귀 종료조건 설정
  
      for (let i = startNumber; i <= n; i++) {
        const newCurrent = [...current]; // 마지막배열만 없애고 나머지 배열은 유지하기위해 부분적으로 초기화.
        newCurrent.push(i); // 배열에 조합 push
        backtracking(newCurrent, i + 1, k - 1); // 재귀호출
      }
    };
    backtracking([], 1, k); // combine 함수를 호출하는 형식이기 때문에
    //combine 함수에서 backtracking 함수를 호출해줘야 backtracking이 동작함
  
    return output; // 정답 반환
  };

 

정답을 저장할 2차원 배열을 선언해주고

 

재귀함수를 작성해줍니다.

n-startnumber +1 < k 조건은 없어도 실행이 되긴합니다만 런타임이 좀 더 늘어납니다.

k===0에 도달하면 재귀가 종료되고 답을 정답배열에 푸시해주는 꼬리재귀형태를 가져요

 

순서만 다르고 요소는 같은 경우 -> [1,2] , [2,1] 같은 경우에는 같은것으로 취급하기때문에

첫 패턴에서 [1,2] [1,3] [1,4] 였다면 [2,3] [2,4] 그 다음은 [3,4] 또 그다음은 [4]

이렇게 startNumber가 1 늘어날때마다 startNumber보다 작은 값은 계산을 안해도 됩니다.

 

즉 배열의 마지막 요소만 바꿔끼워주면 되고

for문이 다음으로 넘어갈때마다 세어야하는 조합은 1개씩 줄어듭니다.

backtracking(newCurrent, i+1, k-1)는 배열길이가 k개만큼 있어야하기때문에

k = 2라면 -1 , -1 두번 동작한 뒤 k==0이 되면서 배열길이가 2에 맞춰질것입니다.