Bài 40 Leetcode: Combination Sum II

Đề bài:

Cho một tập hợp các số ứng cử viên (candidates) và một số mục tiêu (target), tìm tất cả các tổ hợp duy nhất trong candidates sao cho tổng các số ứng cử viên là target. Mỗi số trong candidates chỉ được sử dụng một lần trong mỗi tổ hợp.

Lưu ý: Tập hợp các giải pháp không được chứa các tổ hợp trùng lặp.

Ví dụ 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Ví dụ 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

Ràng buộc:

  • 1 <= độ dài của candidates <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

Giải thích thuật toán bằng C ++

class Solution {
 public:
  vector<vector<int>> combinationSum2(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) {
      if (i > s && A[i] == A[i - 1])
        continue;
      path.push_back(A[i]);
      dfs(A, i + 1, target - A[i], move(path), ans);
      path.pop_back();
    }
  }
};

Đoạn mã trên là một đoạn mã 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 mã:

1. Hàm `combinationSum2` 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 kiểm tra nếu phần tử hiện tại trùng với phần tử trước đó (A[i] == A[i – 1]) và i lớn hơn s, ta bỏ qua phần tử đó để tránh tạo ra các tổ hợp trùng lặp. Nếu không trùng lặp, ta thêm phần tử 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, bỏ qua các phần tử trùng lặp để tránh tạo ra các tổ hợp trùng nhau.

Giải thích thuật toán bằng Java

class Solution {
  public List<List<Integer>> combinationSum2(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) {
      if (i > s && candidates[i] == candidates[i - 1])
        continue;
      path.add(candidates[i]);
      dfs(i + 1, 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 combinationSum2(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.copy())
        return

      for i in range(s, len(candidates)):
        if i > s and candidates[i] == candidates[i - 1]:
          continue
        path.append(candidates[i])
        dfs(i + 1, target - candidates[i], path)
        path.pop()

    candidates.sort()
    dfs(0, target, [])
    return ans

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.