문제링크
간단하게 문제를 설명하자면 이렇습니다.
정수 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에 맞춰질것입니다.
반응형
'leetcode' 카테고리의 다른 글
35. Search insert Position easy (0) | 2022.11.24 |
---|---|
1281. Subtract the Product and Sum of Digits of an Integer (0) | 2022.11.22 |
46. Permutation (0) | 2022.11.18 |
448. Find All Numbers Disappeared in an Array (0) | 2022.11.17 |
39. Combination Sum javascript leetcode (0) | 2022.11.16 |