[Leetcode] 40. Combination Sum II

#조합

Problem

문제 링크

주어진 배열의 요소들을 합하여 target의 값이되는 조합을 구하여하는 문제

Solution

combination sum 요소의 중복을 뺀 방법

• 현재 인덱스를 추가하지않고 뎁스를 이어나가면된다.

JS Code

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  let answer = []
  const dfs = function (comb, sum, curr) {
    if (sum === target) {
      answer.push([...comb])
      return
    }

    for(let nextCurr = curr ; nextCurr < candidates.length; ++nextCurr) {
      if (curr < nextCurr && candidates[nextCurr] === candidates[nextCurr - 1]) continue

      const pick = candidates[nextCurr]
      if (target < sum + pick) break

      comb.push(pick)
      dfs(comb, sum + pick, nextCurr + 1)
      comb.pop()
    }
  }

  candidates.sort((a, b) => a - b)

  dfs([], 0, 0)

  return answer
}