Đề bài:
Cho một mảng gồm các số nguyên phân biệt candidates và một số nguyên mục tiêu target, trả về một danh sách các tổ hợp duy nhất của các số từ candidates mà tổng các số đã chọn là target. Bạn có thể trả về các tổ hợp theo bất kỳ thứ tự nào.
Cùng một số có thể được chọn từ candidates một số lượng không giới hạn. Hai tổ hợp được coi là duy nhất nếu tần suất xuất hiện của ít nhất một số đã chọn là khác nhau.
Các bộ test được tạo ra sao cho số lượng tổ hợp duy nhất có tổng bằng target là ít hơn 150 tổ hợp cho đầu vào đã cho.
Ví dụ 1:
Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Giải thích: 2 và 3 là các số ứng cử viên, và 2 + 2 + 3 = 7. Lưu ý rằng số 2 có thể được sử dụng nhiều lần. 7 là một số ứng cử viên, và 7 = 7. Đây là hai tổ hợp duy nhất.
Ví dụ 2:
Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]
Ví dụ 3:
Input: candidates = [2], target = 1 Output: []
Ràng buộc:
- 1 <= độ dài của candidates <= 30
- 2 <= candidates[i] <= 40
- Tất cả các phần tử trong candidates đều khác nhau)
- 1 <= target <= 40
Giải thích thuật toán bằng C ++
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
ranges::sort(candidates);
dfs(candidates, 0, target, {}, ans);
return ans;
}
private:
void dfs(const vector<int>& A, int s, int target, vector<int>&& path,
vector<vector<int>>& ans) {
if (target < 0)
return;
if (target == 0) {
ans.push_back(path);
return;
}
for (int i = s; i < A.size(); ++i) {
path.push_back(A[i]);
dfs(A, i, target - A[i], move(path), ans);
path.pop_back();
}
}
};
Đoạn code trên là một đoạn code C++ để tạo ra tất cả các tổ hợp duy nhất của các số từ mảng candidates sao cho tổng các số đã chọn là target. Dưới đây là giải thích về thuật toán trong đoạn code:
1. Hàm `combinationSum` nhận một mảng candidates và một số nguyên target là mục tiêu tổng, và trả về một vector chứa tất cả các tổ hợp duy nhất.
2. Ban đầu, ta khởi tạo một vector hai chiều `ans` để lưu trữ các tổ hợp kết quả.
3. Tiếp theo, ta sắp xếp mảng candidates theo thứ tự tăng dần bằng cách sử dụng hàm `sort` từ thư viện Ranges.
4. Sau đó, ta gọi hàm `dfs` để thực hiện đệ quy và tạo ra các tổ hợp duy nhất. Hàm `dfs` nhận vào mảng candidates, vị trí bắt đầu s trong mảng, giá trị target cần đạt được, đường dẫn (path) là các số đã chọn trước đó, và vector `ans` để lưu trữ các tổ hợp kết quả.
5. Trong hàm `dfs`, ta kiểm tra các trường hợp cơ bản. Nếu target nhỏ hơn 0, ta kết thúc đệ quy. Nếu target bằng 0, tức là đã tìm được một tổ hợp duy nhất, ta thêm đường dẫn hiện tại vào vector `ans`.
6. Tiếp theo, ta duyệt qua mảng candidates từ vị trí s đến hết mảng. Đối với mỗi phần tử, ta thêm nó vào đường dẫn và tiếp tục gọi đệ quy `dfs` để tìm các tổ hợp tiếp theo với target được giảm đi giá trị của phần tử đó. Sau khi gọi đệ quy, ta loại bỏ phần tử vừa chọn trong đường dẫn để tiếp tục duyệt các phần tử khác.
7. Sau khi kết thúc vòng lặp, ta đã tạo ra tất cả các tổ hợp duy nhất và lưu trữ chúng trong vector `ans`.
8. Cuối cùng, ta trả về vector `ans` chứa tất cả các tổ hợp duy nhất của các số từ mảng candidates mà tổng các số đã chọn là target.
Thuật toán trên sử dụng phương pháp đệ quy để tạo ra tất cả các tổ hợp duy nhất của các số từ mảng candidates. Quá trình tạo ra các tổ hợp được thực hiện bằng cách duyệt qua mảng candidates và thực hiện đệ quy với các target được giảm dần và đường dẫn được cập nhật. Khi target đạt được giá trị 0, ta đã tìm thấy một tổ hợp duy nhất và thêm nó vào vector kết quả. Quá trình này được lặp lại cho đến khi tạo ra tất cả các tổ hợp duy nhất.
Giải thích thuật toán bằng Java
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(candidates);
dfs(0, candidates, target, new ArrayList<>(), ans);
return ans;
}
private void dfs(int s, int[] candidates, int target, List<Integer> path,
List<List<Integer>> ans) {
if (target < 0)
return;
if (target == 0) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = s; i < candidates.length; ++i) {
path.add(candidates[i]);
dfs(i, candidates, target - candidates[i], path, ans);
path.remove(path.size() - 1);
}
}
}
Giải thích thuật toán bằng Python
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
def dfs(s: int, target: int, path: List[int]) -> None:
if target < 0:
return
if target == 0:
ans.append(path.clone())
return
for i in range(s, len(candidates)):
path.append(candidates[i])
dfs(i, target - candidates[i], path)
path.pop()
candidates.sort()
dfs(0, target, [])
return ans
0 / 5 - (0 Đánh Giá)