Backtracking

Bộ đề bài

Trở lại kỳ thi

1. Subsets

Điểm: 10 (p) Thời gian: 3.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một mảng số nguyên nums gồm các phần tử khác nhau, hãy trả về tất cả các tập con có thể có (tập lũy thừa) của mảng.

Tập kết quả không được chứa các tập con trùng lặp. Có thể trả về kết quả theo bất kỳ thứ tự nào.

Ví dụ

Input Output
nums = [1,2,3] [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
nums = [0] [[],[0]]

Ràng buộc

  • 1 ≤ nums.length ≤ 10
  • -10 ≤ nums[i] ≤ 10
  • Tất cả các phần tử của nums là khác nhau.

2. Combinations

Điểm: 10 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho hai số nguyên n và k, hãy trả về tất cả các tổ hợp có thể gồm k số được chọn từ đoạn [1, n].

Có thể trả về kết quả theo bất kỳ thứ tự nào.

Ví dụ

Input Output Giải thích
n = 4, k = 2 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] Có C(4,2) = 6 tổ hợp. Lưu ý rằng tổ hợp không xét thứ tự, tức là [1,2] và [2,1] được xem là cùng một tổ hợp.
n = 1, k = 1 [[1]] Có C(1,1) = 1 tổ hợp.

Ràng buộc

  • 1 ≤ n ≤ 20
  • 1 ≤ k ≤ n

3. Permutations

Điểm: 10 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một mảng nums gồm các số nguyên khác nhau, hãy trả về tất cả các hoán vị có thể có.

Có thể trả về kết quả theo bất kỳ thứ tự nào.

Ví dụ

Input Output
nums = [1,2,3] [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
nums = [0,1] [[0,1],[1,0]]
nums = [1] [[1]]

Ràng buộc

  • 1 ≤ nums.length ≤ 6
  • -10 ≤ nums[i] ≤ 10
  • Tất cả các số nguyên trong nums là khác nhau.

4. Apple Division

Điểm: 10 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Có n quả táo với trọng lượng đã biết.

Nhiệm vụ của bạn là chia các quả táo thành hai nhóm sao cho độ chênh lệch giữa tổng trọng lượng của hai nhóm là nhỏ nhất.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n: số lượng quả táo.
  • Dòng tiếp theo chứa n số nguyên p1, p2, ..., pn: trọng lượng của từng quả táo.

Kết quả

  • In ra một số nguyên: độ chênh lệch nhỏ nhất giữa tổng trọng lượng của hai nhóm.

Ràng buộc

  • 1 ≤ n ≤ 20
  • 1 ≤ pᵢ ≤ 10^9

Ví dụ

Input Output Giải thích
5
3 2 7 4 1		 1 Nhóm 1 gồm các quả táo có trọng lượng 2, 3 và 4 (tổng trọng lượng 9), nhóm 2 gồm các quả táo có trọng lượng 1 và 7 (tổng trọng lượng 8).

5. Combination Sum

Điểm: 10 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một mảng các số nguyên khác nhau candidates và một số nguyên target, hãy trả về danh sách tất cả các tổ hợp duy nhất của các phần tử trong candidates sao cho tổng các số được chọn bằng target.

Có thể trả về các tổ hợp theo bất kỳ thứ tự nào.

Một số trong candidates có thể được chọn không giới hạn số lần.

Hai tổ hợp được xem là khác nhau nếu tần suất xuất hiện của ít nhất một số được chọn là khác nhau.

Các bộ test được tạo sao cho số lượng tổ hợp duy nhất có tổng bằng target nhỏ hơn 150.

Ví dụ 1

Input Output
candidates = [2,3,6,7], target = 7 [[2,2,3],[7]]

Giải thích

  • 2 và 3 là các phần tử trong candidates, 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 phần tử trong candidates, và 7 = 7.
  • Đây là hai tổ hợp duy nhất.

Ví dụ 2

Input Output
candidates = [2,3,5], target = 8 [[2,2,2,2],[2,3,3],[3,5]]

Ví dụ 3

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

6. Combination Sum II

Điểm: 10 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một tập hợp các số ứng viên candidates và một số mục tiêu target, hãy tìm tất cả các tổ hợp duy nhất trong candidates sao cho tổng các số được chọn bằng target.

Mỗi số trong candidates chỉ được sử dụng một lần trong một tổ hợp.

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

Ví dụ 1

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

Ví dụ 2

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

Ràng buộc

  • 1 ≤ candidates.length ≤ 100
  • 1 ≤ candidates[i] ≤ 50
  • 1 ≤ target ≤ 30

7. Partition Equal Subset Sum

Điểm: 10 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một mảng số nguyên nums, hãy trả về true nếu có thể chia mảng thành hai tập con sao cho tổng các phần tử của hai tập con bằng nhau, ngược lại trả về false.

Ví dụ

Input Output Giải thích
nums = [1,5,11,5] true Mảng có thể được chia thành hai tập con [1,5,5] và [11].
nums = [1,2,3,5] false Không thể chia mảng thành hai tập con có tổng bằng nhau.

Ràng buộc

  • 1 ≤ nums.length ≤ 200
  • 1 ≤ nums[i] ≤ 100