[Leetcode] 39. Combination Sum

#조합, #DFS

Problem

문제 링크

후보리스트에서 중복을 허용하여 합했을 때 target이 나오는 경우를 구한다.

Solution

DFS를 이용하여 배열의 순서대로 depth로 들어간다. 깊은 뎁스로 이동 하면서 해당 인덱스의 값을 더하고, 그 값이 target과 일치하면 저장, 초과하면 함수를 리턴시켜 더이상 깊은 뎁스로 진입하는 것을 멈춘다.

반복문을 이용하여 모든 경우의 수에 대한 계산을 진행한다.

DFS를 이용한 TS Code

function combinationSum(candidates: number[], target: number): number[][] {
  let answer:number[][] = []
  const DFS = (sum: number, pack: number[], idx: number) => {
    if (target === sum) {
      answer.push([...pack])
      return
    }
    if (target < sum) return

    for(let i = idx; i < candidates.length; i++) {
      const candidate = candidates[i]
      DFS(
        sum + candidate,
        [...pack, candidate],
        i
      )
    }
  }

  DFS(0, [], 0)

  return answer
};

Combination 알고리즘을 이용한 JS Code

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

  function doCombination(idx, pickeds) {
    const sum = pickeds.reduce((acc, cur) => acc + cur, 0)
    if (target < sum) return
    if (target === sum) {
      answer.push([...pickeds])
      return
    }

    for (let i = idx; i < candidates.length; i++) {
      pickeds.push(candidates[i])
      doCombination(i, pickeds)
      pickeds.pop()
    }
  }

  doCombination(0, [])

  return answer
}