LeetCode 39 - Combination Sum (Medium)

문제

LeetCode - 39번

풀이 과정

중복 조합 을 만들어서 숫자들의 합이 target 이 되는 모든 경우를 찾는 문제입니다.

여기서 중복 조합 이란 서로 다른 n개를 중복을 허용하여 r 개를 선택하는 경우 를 말합니다.
이를 위해서는 백트래킹 을 활용해서 모든 조합을 탐색해주는 과정이 필요합니다.

기존 조합에서는 i 번쩨 숫자를 선택했을 경우 그 다음 숫자인 i + 1 번째 부터 하나씩 골라야하지만
중복을 허용하기 때문에 선택 시작점을 i 번째 부터 해주면 됩니다.

코드

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
  const answer = [];

  function combination(start, sum, selected) {
    if (sum > target) return;
    else if (sum === target) answer.push(selected);

    for (let i = start; i < candidates.length; i++) {
      combination(i, sum + candidates[i], [...selected, candidates[i]]);
    }
  }

  combination(0, 0, []);
  return answer;
};