💡 풀이
var combinationSum = function (candidates, target) {
let answer = [];
const backTracking = (prevIndex, targetSum, comb) => {
if (targetSum === 0) answer.push([...comb]);
else if (targetSum < 0) return;
for (let i = prevIndex; i < candidates.length; i++) {
comb.push(candidates[i]);
backTracking(i, targetSum - candidates[i], comb);
comb.pop();
}
};
backTracking(0, target, []);
// console.log('answer: ', answer);
return answer;
};
let candidates = [1, 2, 3];
let target = 5;
combinationSum(candidates, target);
// 선택된 것보다 작은 수는 안된다.(조합 경우에서 중복을 피하기 위해)
// 선택된 경우(decision space) 1, 2, 3
// 4 3 2
// 1,2,3 2,3 3📝 결과
📝 정리
backTracking을 통해 풀었다. 조합(Combination)이 순열(Permutation)과 다른 점은 unique해야 한다는 것인데, 이 말은 target=5라고 했을 때, [1,2,2]와 [2,1,2]는 다른 경우가 아니라 같은 경우라는 뜻이다.
조합은 순서가 없고, 순열은 순서가 있다고 생각하면 된다.
풀이는 다음과 같다.
-
답을 담을
answer배열을 준비한다. -
backTracking함수를 선언한다. 이전 문제 Permutation(순열)과 유사하다. 종료 조건으로는targetSum === 0과targetSum < 0, 이렇게 두 가지를 준비해준다. -
targetSum === 0인 경우는 답이 되는 경우기 때문에answer배열에comb의 복사본을push해주고,0보다 작아진 경우에는 답이 안되는 경우기 때문에 함수 호출만 종료해준다. (=return ;) -
이제 경우의 수를 필터링 하는 경우를 살펴보자. 순열 문제를 풀 때는
i가0부터 시작했지만, 조합의 경우는 위에서 말했듯이 중복을 허용하지 않기 때문에(unique) 이전에 탐색했던 index는 탐색하지 않아야 한다. 따라서prevIndex라는 파라미터를 반복문의i에 담아준다. -
재귀 호출할
backTracking함수에는 인자로i와targetSum - candidates[i], comb를 넣어주는데,targetSum - candidates[i]가 무슨 뜻이냐면 - coinChange 문제를 생각해보면 된다. coinChange 문제를 풀 때, 동전coins = [1, 2, 5]가 있고,target=11이라고 했을 때,target에서 각coins[i]를 빼주는 식으로(10, 9, 6) 경우의 수를 탐색해나갔다. 같은 방식으로 이 문제에서도 경우의 수를 탐색해 나가는 것이다.
++ 이 문제를 풀 때 계속 RangeError: Maximum call stack size exceeded, 즉 Stackoverflow가 발생했었는데.. 원래 이렇게 됐어야 하는 함수 호출 종료 조건이
// 정답
if (targetSum === 0) answer.push([...comb]);
else if (targetSum < 0) return;// 삽질
if (target === 0) answer.push([...comb]);
else if (target < 0) return;이렇게 되어 있었다.. 당연히 target이 0 근처로도 가지 않으니 무한 루프에 빠진건데 하하하ㅏ 계속 잘못된게 없는 것 같은데? 이러면서 20분을 날리고 스터디원 분께 헬프를 요청했었다.
변수명 잘 확인하자.
수정, 지적을 환영합니다!
문제 링크
https://leetcode.com/problems/combination-sum/
