후보리스트에서 중복을 허용하여 합했을 때 target
이 나오는 경우를 구한다.
DFS를 이용하여 배열의 순서대로 depth로 들어간다. 깊은 뎁스로 이동 하면서 해당 인덱스의 값을 더하고, 그 값이 target과 일치하면 저장, 초과하면 함수를 리턴시켜 더이상 깊은 뎁스로 진입하는 것을 멈춘다.
반복문을 이용하여 모든 경우의 수에 대한 계산을 진행한다.
/**
* @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
}