← 17주차 · 백트래킹
어려움백트래킹

합이 target인 조합

서로 다른 양의 정수 배열 candidates와 정수 target이 주어져요. candidates에서 몇 개를 골라(각 수는 최대 한 번) 합이 정확히 target이 되는 모든 조합을 담아 반환해요.

순서만 다른 같은 조합은 한 번만 세요. [2, 5]와 [5, 2]는 같은 조합이에요. 그래서 다음 후보는 항상 자기 다음 인덱스부터 봐요.

정렬해 두면 가지치기를 할 수 있어요. 남은 목표보다 큰 후보를 만나면, 그 뒤 후보는 더 크니 볼 필요 없이 멈춰도 돼요.

조합들의 순서와 각 조합 안 원소의 순서는 채점에서 신경 쓰지 않아요.

예시

예시 1
입력
candidates = [2, 3, 6, 7], target = 7
출력
[[7]]
설명
합이 7이 되는 조합은 [7] 하나뿐이에요(각 수는 한 번씩).
예시 2
입력
candidates = [2, 3, 5], target = 8
출력
[[3, 5]]
설명
합이 8인 조합은 3 + 5뿐이에요.
예시 3
입력
candidates = [2, 3, 4, 6], target = 6
출력
[[2, 4], [6]]
설명
2 + 4 = 6, 그리고 6 자체예요. 순서는 달라도 괜찮아요.

제한 사항

  • 1 ≤ candidates.length ≤ 20
  • candidates의 값은 서로 다른 양수예요.
  • 1 ≤ candidates[i] ≤ 100, 1 ≤ target ≤ 500
후보를 오름차순으로 정렬하고 backtrack(start, remain)을 만들어요. remain이 0이면 완성이라 복사본을 담아요. start부터 후보를 보되, 후보가 remain보다 크면 뒤는 볼 필요 없으니 멈춰요. 아니면 넣고 backtrack(i + 1, remain - 후보)로 진행한 뒤 되돌려요.
javascript
function combinationSum(candidates, target) {
  const sorted = [...candidates].sort((a, b) => a - b);
  const out = [];
  const path = [];
  function backtrack(start, remain) {
    if (remain === 0) {
      out.push([...path]);
      return;
    }
    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remain) break;
      path.push(sorted[i]);
      backtrack(i + 1, remain - sorted[i]);
      path.pop();
    }
  }
  backtrack(0, target);
  return out;
}
이전 문제순열 생성
다음 문제N-Queen
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.