39. Combination Sum - medium
문제
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
제한사항
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
입출력 예
1
2
3
4
5
6
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
1
2
3
4
5
6
7
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
풀이
- Recursive, BackTracking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
void backTracking(vector<vector<int>>& ans, vector<int>& candidates, vector<int>& curItem, int target, int cur, int begin){
// 현재 값이 target과 같으면 리턴
if(cur == target){
ans.push_back(curItem);
return;
}
// 같은 내용이 반복되지 않도록 candidates의 index를 0 부터 candidates.size() 까지
// candidates의 index를 매개변수로 하여 중복 방지
for(auto i = begin ; i < candidates.size() ; ++i){
// 현재 값 + candidates[i] 이 target보다 작거나 같아야 해당 candidates[i]를 추가
// 재귀로 BackTracking 수행후, pop을 하여 중복되는 원소 제거
if(candidates[i] + cur <= target){
curItem.push_back(candidates[i]);
backTracking(ans, candidates, curItem, target, cur + candidates[i], i);
curItem.pop_back();
}
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> answer;
vector<int> item;
backTracking(answer, candidates, item, target, 0, 0);
return answer;
}
};