LeetCode - 조합 합계
24939 단어 gojavascriptalgorithmsprogramming
문제 설명
개별 정수 후보의 배열과 대상 정수 대상이 주어지면 선택한 숫자가 대상으로 합산되는 모든 고유한 후보 조합 목록을 반환합니다. 순서에 상관없이 조합을 반환할 수 있습니다.
후보자 중에서 동일한 번호를 무제한으로 선택할 수 있습니다. 선택한 숫자 중 적어도 하나의 빈도가 다른 경우 두 조합은 고유합니다.
목표에 합산되는 고유한 조합의 수가 주어진 입력에 대해 150개 미만의 조합임을 보장합니다.
다음에서 가져온 문제 설명: https://leetcode.com/problems/combination-sum/ .
예 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.
예 2:
Input: candidates = [2, 3, 5], target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
예 3:
Input: candidates = [2], target = 1
Output: []
제약:
- 1 <= candidates.length <= 30
- 1 <= candidates[i] <= 200
- All elements of candidates are distinct.
- 1 <= target <= 500
설명
무차별 대입 방식
무차별 대입 접근 방식은 모든 조합을 생성하고 배열의 요소가 대상에 합산되는지 확인하는 것입니다.
그러나 위 프로그램의 시간 복잡도는 O(N^2)가 됩니다.
역추적
이러한 종류의 문제는 역추적을 사용하여 해결할 수 있습니다. 배열 요소를 임시 배열(현재라고 함)에 계속 추가하고 이 임시 배열의 요소 합계를 계속 추적하는 재귀 함수를 작성합니다. 재귀 함수 내에서 두 가지 기본 사례를 유지합니다.
위의 접근 방식을 명확하게 이해하기 위해 알고리즘을 확인합시다.
- initialize the result as a 2D array
initialize current as an array
// n = index, at start it will be 0.
// sumTillNow = sum of the current elements in the array, at the start it will be 0
// current = current list of elements in the array, at the start it will be an empty array []
- call combinationSumUtil(result, candidates, n, target, sumTillNow, current)
- return result
// combinationSumUtil function
- if sumTillNow == target
// append current to result
- result.push_back(current)
- if sumTillNow > target
- return
- loop for i = n; i <= candidates.size() - 1; i++
// append candidates array ith element to the current array
- current.push_back(candidates[i])
- sumTillNow += candidates[i]
// call the function recursively
- combinationSumUtil(result, candidates, i, target, sumTillNow, current)
- sumTillNow -= current[current.size() - 1]
// remove the last element from the array
- current.pop_back()
C++, Golang 및 Javascript의 솔루션을 확인해 봅시다.
C++ 솔루션
class Solution {
public:
void combinationSumUtil(vector<vector<int>>& result, vector<int>& candidates, int n, int target, int sumTillNow, vector<int>& current) {
if(sumTillNow == target) {
result.push_back(current);
}
if(sumTillNow > target) {
return;
}
for(int i = n; i <= candidates.size() - 1; i++) {
current.push_back(candidates[i]);
sumTillNow += candidates[i];
combinationSumUtil(result, candidates, i, target, sumTillNow, current);
sumTillNow -= current[current.size() - 1];
current.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> current;
combinationSumUtil(result, candidates, 0, target, 0, current);
return result;
}
};
골랑 솔루션
func combinationSumUtil(result *[][]int, candidates []int, n, target, sumTillNow int, current []int) {
if sumTillNow == target {
*result = append(*result, append([]int{}, current...))
return
}
if sumTillNow > target {
return
}
for i := n; i <= len(candidates) - 1; i++ {
current = append(current, candidates[i])
sumTillNow = sumTillNow + candidates[i]
combinationSumUtil(result, candidates, i, target, sumTillNow, current)
sumTillNow = sumTillNow - current[len(current) - 1]
current = current[:len(current) - 1]
}
}
func combinationSum(candidates []int, target int) [][]int {
result := make([][]int, 0)
combinationSumUtil(&result, candidates, 0, target, 0, []int{})
return result
}
자바스크립트 솔루션
var combinationSum = function(candidates, target) {
let result = [];
const combinationSumUtil = (candidates, n, target, sumTillNow, current) => {
if(sumTillNow === target) {
result.push([...current]);
}
if(sumTillNow > target) {
return;
}
for(let i = n; i <= candidates.length - 1; i++){
current.push(candidates[i]);
sumTillNow += candidates[i];
combinationSumUtil(candidates, i, target, sumTillNow, current);
sumTillNow -= current[current.length - 1];
current.pop();
}
}
combinationSumUtil(candidates, 0, target, 0, []);
return result;
};
알고리즘을 시험 실행해 봅시다.
Input: candidates = [2, 3, 6, 7]
target = 7
// combinationSum function
Step 1: vector<vector<int>> result
vector<int> current
Step 2: combinationSumUtil(result, candidates, 0, target, 0, current)
// combinationSumUtil function
Step 3: if sumTillNow == target
0 == 7
false
if sumTillNow > target
0 > 7
false
loop for int i = n; i <= candidates.size() - 1
i = 0
i <= 4 - 1
0 <= 3
true
current.push_back(candidates[i])
current.push_back(candidates[0])
current.push_back(2)
current = [2]
sumTillNow += candidates[i]
= sumTillNow + candidates[0]
= 0 + 2
= 2
combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 2, [2])
Step 4: if sumTillNow == target
2 == 7
false
if sumTillNow > target
2 > 7
false
loop for int i = n; i <= candidates.size() - 1
i = 0
i <= 4 - 1
0 <= 3
true
current.push_back(candidates[i])
current.push_back(candidates[0])
current.push_back(2)
current = [2, 2]
sumTillNow += candidates[i]
= sumTillNow + candidates[0]
= 2 + 2
= 4
combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 4, [2, 2])
Step 5: if sumTillNow == target
4 == 7
false
if sumTillNow > target
4 > 7
false
loop for int i = n; i <= candidates.size() - 1
i = 0
i <= 4 - 1
0 <= 3
true
current.push_back(candidates[i])
current.push_back(candidates[0])
current.push_back(2)
current = [2, 2, 2]
sumTillNow += candidates[i]
= sumTillNow + candidates[0]
= 4 + 2
= 6
combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 6, [2, 2, 2])
Step 6: if sumTillNow == target
6 == 7
false
if sumTillNow > target
6 > 7
false
loop for int i = n; i <= candidates.size() - 1
i = 0
i <= 4 - 1
0 <= 3
true
current.push_back(candidates[i])
current.push_back(candidates[0])
current.push_back(2)
current = [2, 2, 2, 2]
sumTillNow += candidates[i]
= sumTillNow + candidates[0]
= 6 + 2
= 8
combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 8, [2, 2, 2, 2])
Step 7: if sumTillNow == target
8 == 7
false
if sumTillNow > target
8 > 7
true
return
we backtrack to step 6 and continue
Step 8: combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 8, [2, 2, 2, 2])
sumTillNow = sumTillNow - current[len(current) - 1]
= 8 - current[4 - 1]
= 8 - current[3]
= 8 - 2
= 6
current.pop_back()
current = [2, 2, 2]
i++
i = 1
i = 1
i <= 4 - 1
1 <= 3
true
current.push_back(candidates[i])
current.push_back(candidates[1])
current.push_back(3)
current = [2, 2, 2, 3]
sumTillNow += candidates[i]
= 6 + candidates[1]
= 6 + 3
= 9
combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 9, [2, 2, 2, 3])
Step 9: if sumTillNow == target
9 == 7
false
if sumTillNow > target
9 > 7
true
return
we backtrack to step 8 and continue
Step 10:combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 9, [2, 2, 2, 3])
sumTillNow = sumTillNow - current[len(current) - 1]
= 9 - current[4 - 1]
= 9 - current[3]
= 9 - 3
= 6
current.pop_back()
current = [2, 2, 2]
i++
i = 2
i = 2
i <= 4 - 1
2 <= 3
true
current.push_back(candidates[i])
current.push_back(candidates[2])
current.push_back(6)
current = [2, 2, 2, 6]
sumTillNow += candidates[i]
= 6 + candidates[2]
= 6 + 6
= 12
combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 12, [2, 2, 2, 6])
Step 11: if sumTillNow == target
12 == 7
false
if sumTillNow > target
12 > 7
true
return
we backtrack to step 10 and continue
Step 12:combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 9, [2, 2, 2, 3])
sumTillNow = sumTillNow - current[len(current) - 1]
= 12 - current[4 - 1]
= 12 - current[3]
= 12 - 6
= 6
current.pop_back()
current = [2, 2, 2]
i++
i = 3
i = 3
i <= 4 - 1
3 <= 3
true
current.push_back(candidates[i])
current.push_back(candidates[3])
current.push_back(7)
current = [2, 2, 2, 7]
sumTillNow += candidates[i]
= 6 + candidates[3]
= 6 + 7
= 13
combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 13, [2, 2, 2, 7])
Step 13: if sumTillNow == target
13 == 7
false
if sumTillNow > target
13 > 7
true
return
we backtrack to step 12 and continue
Step 14:combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 9, [2, 2, 2, 3])
sumTillNow = sumTillNow - current[len(current) - 1]
= 13 - current[4 - 1]
= 13 - current[3]
= 13 - 7
= 6
current.pop_back()
current = [2, 2, 2]
i++
i = 4
i = 3
i <= 4 - 1
4 <= 3
false
We return to Step 5 directly
Step 15:combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 6, [2, 2, 2])
sumTillNow = sumTillNow - current[len(current) - 1]
= 6 - current[3 - 1]
= 6 - current[2]
= 6 - 2
= 4
current.pop_back()
current = [2, 2]
i++
i = 1
i = 1
i <= 4 - 1
1 <= 3
true
current.push_back(candidates[i])
current.push_back(candidates[1])
current.push_back(3)
current = [2, 2, 3]
sumTillNow += candidates[i]
= 4 + candidates[1]
= 4 + 3
= 7
combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 7, [2, 2, 3])
Step 16:if sumTillNow == target
7 == 7
true
result.push_back(current)
result.push_back([2, 2, 3])
result = [[2, 2, 3]]
Similarly, we iterate over all other elements and get the result as
[[2, 2, 3], [7]]
Reference
이 문제에 관하여(LeetCode - 조합 합계), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/_alkesh26/leetcode-combination-sum-2338텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
