문제링크
input & output
Example 1
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
- Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3
Input: candidates = [2], target = 1
Output: []
Example 4
Input: candidates = [1], target = 1
Output: [[1]]
Example 5
Input: candidates = [1], target = 2
Output: [[1,1]]
Approach #1
/*
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
0) candidates[i]===target이면 res에 can[i]추가하고 최종배열에 바로 넣음
1) target-candidates[i]를 배열에서 찾는다.
2) 없으면, 한번더 candidates[i]를 빼고 배열에서 남은 숫자를 찾는다.
....
4) 있으면 res배열에 추가, 없으면 res배열 비운다.(시작할때 빈배열에서 시작하도록)
5) 백트래킹(?)
7/2=3
7
*/Solution #1
var combinationSum = function(candidates, target) {
const result = [];
const list=[];
backtracking(result, list, candidates, target, 0);
return result;
};
// 2, 2, 2, 2
function backtracking(result, tempList, nums, remain, start) {
//console.log(nums);
if (remain < 0) return;
else if (remain === 0) return result.push([...tempList]);
console.log(tempList);
for (let i=start; i<nums.length; i++) {
tempList.push(nums[i]);
backtracking(result, tempList, nums, remain-nums[i], i);
tempList.pop();
}
}Time Complexity
O(C^T)
C: candidates.length
T: target size
candidates 길이만큼 반복문을 돌며 해당 요소가 target을 만들수 있는 숫자인지 확인하는데, target숫자가 되는 조합이 나올때까지 재귀를 들어가며 계속 확인한다.
이때 1,1,1,1.... 이런식으로 target의 크기만큼 1이 구성되는것이 가장 깊은 재귀일 것이기 때문에 시간복잡도는 C^T가 될것이다.
Space Complexity
O(T) -> 재귀 제일 깊을때 [1,1,1,1 ..... ]
T: target size
마찬가지로 콜스택이 가장 깊게 쌓이는 경우는 1,1,1,1.... target숫자만큼 1이 쌓이는 경우이기 때문에 공간복잡도는 T.
Solution #2
var combinationSum = function(candidates, target) {
const result=[];
if(candidates.length===1 && candidates[0]>target) return result;
let c=0;
const dfs = (c,sum,arr) =>{
// 타깃보다 크면 return;
// 타깃과 같으면 정답에 추가하고 return;
// 타깃보다 작으면 recursion
if(c>=candidates.length) return;
if(sum>target) return;
if(sum===target){
result.push([...arr]);
return;
}
//recursion
for(let i=c; i < candidates.length ; i++){
arr.push(candidates[i]); //[2,2,2,1]
dfs(i,sum+candidates[i],arr); // dfs(c,2,[2])
arr.pop();
}
};
dfs(c,0,[]);
return result;
};Time Complexity
O(C^T)
C: candidates.length
T: target size
candidates 길이만큼 반복문을 돌며 해당 요소가 target을 만들수 있는 숫자인지 확인하는데, target숫자가 되는 조합이 나올때까지 재귀를 들어가며 계속 확인한다.
이때 1,1,1,1.... 이런식으로 target의 크기만큼 1이 구성되는것이 가장 깊은 재귀일 것이기 때문에 시간복잡도는 C^T가 될것이다.
Space Complexity
O(T) -> 재귀 제일 깊을때 [1,1,1,1 ..... ]
T: target size
마찬가지로 콜스택이 가장 깊게 쌓이는 경우는 1,1,1,1.... target숫자만큼 1이 쌓이는 경우이기 때문에 공간복잡도는 T.
