주어진 배열의 요소들을 합하여 target
의 값이되는 조합을 구하여하는 문제
combination sum 요소의 중복을 뺀 방법
/**
* @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
}