문제를 푸는 기준

함수 한 번이 무엇을 의미하는지 한 문장으로 정의합니다. 재귀가 끝난 뒤 상태를 복원해야 형제 가지가 서로 영향을 주지 않습니다.

핵심 개념

대표 문제

중복 없는 k개 조합

정수 배열 numbers와 k가 주어집니다. 값이 같은 조합은 한 번만 포함하고 오름차순 조합 배열을 반환하세요.

함수 시그니처: solution(numbers, k)

제한사항

• numbers의 길이는 1 이상 15 이하입니다.
• k는 0 이상 numbers의 길이 이하입니다.

입출력 예

풀이 설계

1. 배열을 정렬해 같은 값을 이웃하게 만듭니다.
2. start 뒤 후보를 path에 넣고 재귀 호출합니다.
3. 같은 깊이의 같은 값은 건너뛰고 호출 뒤 pop합니다.

JavaScript 풀이

function solution(numbers, k) {
  const sorted = [...numbers].sort((a, b) => a - b);
  const result = [];
  const path = [];
 
  const backtrack = (start) => {
    if (path.length === k) {
      result.push([...path]);
      return;
    }
    for (let i = start; i < sorted.length; i += 1) {
      if (i > start && sorted[i] === sorted[i - 1]) continue;
      path.push(sorted[i]);
      backtrack(i + 1);
      path.pop();
    }
  };
 
  backtrack(0);
  return result;
}

복잡도

• 시간복잡도: O(C(n, k) × k)
• 공간복잡도: O(k)
• 핵심 패턴: 선택하고 재귀 호출한 뒤 상태 복원
• 경계 사례: k가 0이면 빈 조합 하나 반환

연습 문제

1. 모든 순열

서로 다른 값의 모든 순열을 반환하세요.

2. 목표 합 조합

후보를 중복 사용해 target을 만드는 조합을 반환하세요.

3. 격자 단어 찾기

인접 칸으로 단어를 만들 수 있는지 반환하세요.

자주 하는 실수

• 종료 조건이 없는 실수
• path 복사본이 아닌 원본을 결과에 넣는 실수
• pop을 빠뜨리는 실수
• 중복 제거 조건을 모든 깊이에 잘못 적용하는 실수

핵심 정리

• 함수 시그니처와 반환 자료형을 먼저 확정합니다.
• 제한사항으로 가능한 시간복잡도를 판단합니다.
• 예시와 경계 사례를 손으로 추적한 뒤 구현합니다.
• 완성한 solution 함수가 입력을 불필요하게 바꾸지 않는지도 확인합니다.

확인 문제

참고 자료

• MIT OpenCourseWare 6.006 Introduction to Algorithms 
• 프로그래머스 코딩테스트 고득점 Kit 
• MDN Array