100 bài toán có thể áp dụng thuật toán quay lui trong lập trình

Thuật toán quay lui (backtracking algorithm) là một phương pháp mạnh mẽ trong lập trình để giải quyết các vấn đề có tính chất tổ hợp hoặc có cấu trúc lặp lại. Nó được sử dụng khi bạn cần tìm tất cả các giải pháp hoặc một giải pháp tối ưu cho một vấn đề cụ thể.

Thuật toán quay lui thường có thời gian chạy lâu hơn đối với các vấn đề lớn, nhưng nó đưa ra các giải pháp chính xác hoặc tìm kiếm tất cả các giải pháp có thể. Điều này làm cho nó trở thành một công cụ quan trọng trong việc giải quyết nhiều bài toán thú vị trong lập trình và khoa học máy tính.

Dưới đây là 100 bài toán giúp các bạn có thể rèn luyện tốt kỹ năng lập trình với việc sử dụng thuật toán quay lui:

1. Tìm tất cả các hoán vị của một danh sách số nguyên.
2. Tìm tất cả các tổ hợp của một danh sách số nguyên.
3. Giải bài toán N-queens (xếp hậu).
4. Giải bài toán Sudoku.
5. Tìm xâu con có độ dài k của một chuỗi.
6. Tìm tất cả các con đường trong đồ thị.
7. Tìm kiếm xâu con chung dài nhất của hai chuỗi.
8. Tìm kiếm tất cả các đường đi ngắn nhất trong đồ thị (Thuật toán Dijkstra).
9. Tạo tất cả các dãy con của một mảng.
10. Tìm tất cả các cách để tạo một số nguyên bằng cách cộng các số trong một mảng (tìm số nhóm con).
11. Tạo tất cả các cấu hình hợp lệ của một bảng chữ cái (tìm các hoán vị của bảng chữ cái).
12. Tạo tất cả các dãy số tăng dần có độ dài k từ một dãy số nguyên cho trước.
13. Giải bài toán cắt que tái nguyên (Cutting Stock Problem).
14. Tìm các con đường không trùng lặp trong đồ thị có hướng (Thuật toán Hamiltonian Cycle).
15. Tìm tất cả các cách để tạo một số nguyên bằng cách nhân các số trong một mảng (tìm số nhóm con).
16. Tìm tất cả các tập con có tổng bằng một giá trị cụ thể trong mảng (tìm số nhóm con).
17. Tìm tất cả các hoán vị của một xâu ký tự không trùng lặp.
18. Tạo tất cả các hoán vị của một tập hợp ký tự.
19. Tạo tất cả các phân chia của một số nguyên dương n (Partition Problem).
20. Giải bài toán 8 quân hậu trên bàn cờ 8×8.
21. Tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng n (Sieve of Eratosthenes).
22. Tạo tất cả các cách chia một số nguyên thành tổng các số nguyên dương (tính toán tổ hợp).
23. Tìm tất cả các dãy con liên tục có tổng bằng một giá trị cụ thể trong mảng.
24. Tìm tất cả các dãy con không liên tục có tổng bằng một giá trị cụ thể trong mảng.
25. Tạo tất cả các dãy con tăng dần từ một mảng.
26. Tìm tất cả các cách để tạo một số nguyên bằng cách sử dụng các toán tử +, -, *, / trên một mảng các số.
27. Tạo tất cả các dãy con không liên tục có tổng là số nguyên tố từ mảng.
28. Tìm tất cả các hoán vị của một danh sách đối tượng.
29. Tạo tất cả các cách chia một số nguyên thành các số nguyên tố (Prime Partition).
30. Tìm tất cả các cách chia một số nguyên thành các số Fibonacci (Fibonacci Partition).
31. Giải bài toán TSP (Traveling Salesman Problem) bằng thuật toán quay lui.
32. Tạo tất cả các cách chia một số nguyên thành các số nguyên dương không lặp lại (Distinct Partition).
33. Tạo tất cả các dãy con tăng dần không liên tục từ một mảng.
34. Tìm tất cả các số nguyên tố liên tiếp trong một khoảng cho trước.
35. Giải bài toán N-queens sử dụng giải thuật quay lui cắt tỉa (Backtracking with Pruning).
36. Tạo tất cả các cách chia một số nguyên thành các số chia hết cho 3 (3-Partition Problem).
37. Tìm tất cả các đường đi từ một đỉnh đến một đỉnh khác trong đồ thị có trọng số (All Paths in Weighted Graph).
38. Tìm tất cả các con đường từ một đỉnh đến một đỉnh khác trong đồ thị có hướng (All Paths in Directed Graph).
39. Tạo tất cả các hoán vị của một danh sách các đối tượng theo một số quy tắc cụ thể.
40. Tạo tất cả các dãy con không trùng lặp từ một mảng.
41. Tìm tất cả các dãy con có tổng lớn nhất từ mảng.
42. Tạo tất cả các hoán vị của một xâu ký tự có phần tử trùng lặp.
43. Tạo tất cả các dãy con có tổng nhỏ nhất từ mảng.
44. Tìm tất cả các cách xếp hậu trên bàn cờ n x n sao cho không có hai quân hậu nào ăn nhau.
45. Giải bài toán n-queens sử dụng đệ quy quay lui cắt tỉa (Backtracking with Pruning).
46. Tạo tất cả các dãy con tăng dần không liên tục từ một mảng sắp xếp.
47. Tạo tất cả các dãy con giảm dần không liên tục từ một mảng sắp xếp.
48. Tìm tất cả các đường đi từ một đỉnh đến một đỉnh khác trong đồ thị có trọng số, sao cho tổng trọng số nhỏ nhất (All Shortest Paths in Weighted Graph).
49. Tạo tất cả các cách chia một số nguyên thành các số nguyên tố cộng thêm một số cụ thể (Prime Partition with Fixed Sum).
50. Tìm tất cả các cách để tạo một số nguyên bằng cách sử dụng toán tử +, -, *, / trên một mảng các số và có thể có dấu ngoặc.
51. Tìm tất cả các hoán vị của một danh sách số.
52. Tìm tất cả các tổ hợp của một danh sách số với một số ký tự cố định.
53. Tìm tất cả các hoán vị của một chuỗi ký tự.
54. Tìm tất cả các tổ hợp của một chuỗi ký tự với một số ký tự cố định.
55. Tìm tất cả các xâu con không trùng lặp của một chuỗi ký tự.
56. Tìm xem có tồn tại một xâu con trong một chuỗi ký tự cho trước hay không.
57. Tìm kiếm xem một xâu con có tồn tại trong một lưới ký tự (bảng chữ cái) hay không.
58. Tìm tất cả các con đường trong một đồ thị từ một đỉnh đến một đỉnh khác bằng thuật toán tìm kiếm theo chiều sâu (DFS).
59. Tìm tất cả các đường đi từ một đỉnh xuất phát đến một đỉnh đích trong một đồ thị bằng thuật toán tìm kiếm theo chiều rộng (BFS).
60. Tìm kiếm đường đi ngắn nhất trong một đồ thị có trọng số bằng thuật toán Dijkstra.
61. Tìm kiếm đường đi ngắn nhất trong một đồ thị có trọng số âm bằng thuật toán Bellman-Ford.
62. Tìm kiếm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị bằng thuật toán Floyd-Warshall.
63. Giải bài toán N-Queens (xếp hậu) để đặt N con hậu trên bàn cờ NxN sao cho chúng không tấn công nhau.
64. Giải bài toán Sudoku bằng thuật toán quay lui.
65. Tìm tất cả các cách xếp một số các vật phẩm vào một túi sao cho tổng trọng lượng không vượt quá một giới hạn bằng thuật toán “Knapsack Problem”.
66. Giải bài toán “Traveling Salesman” để tìm đường đi ngắn nhất qua tất cả các thành phố một lần và quay về thành phố xuất phát.
67. Tìm tất cả các cách xếp một số các thành phần thành một tập hợp con của một tập hợp lớn.
68. Tìm tất cả các số nguyên dương nhỏ hơn hoặc bằng N mà tổng các chữ số bằng S.
69. Tìm tất cả các cách chia một số nguyên N thành tổng của các số nguyên dương nhỏ hơn hoặc bằng M.
70. Tìm tất cả các hoán vị của các từ trong một danh sách từ vựng.
71. Tìm tất cả các cách sắp xếp một danh sách từ vựng theo thứ tự từ điển.
72. Tìm tất cả các định dạng chuỗi hợp lệ của ngoặc đơn.
73. Tìm tất cả các cách xếp các số nguyên từ 1 đến N vào một bảng kích thước NxN sao cho không có hai số nào cùng hàng hoặc cùng cột.
74. Tìm tất cả các con đường trong một mê cung để đạt được đích.
75. Giải bài toán “Crossword Puzzle” để điền các từ vào một lưới ô chữ.
76. Tìm tất cả các cách xếp các khối hình thành một hình hộp chứa bằng thuật toán “Packing Problem”.
77. Tìm tất cả các đồ thị con liên thông trong một đồ thị không liên thông.
78. Tìm tất cả các dãy số con liên tiếp có tổng bằng một số nguyên đã cho.
79. Giải bài toán “Word Search” để tìm tất cả các từ trong một lưới ký tự.
80. Tìm tất cả các cách xếp các biểu thức toán học có kết quả bằng một giá trị đã cho.
81. Tìm tất cả các hình học học có thể được vẽ bằng cách nối các điểm đã cho.
82. Tìm tất cả các dãy số Fibonacci nhỏ hơn hoặc bằng một số nguyên N.
83. Giải bài toán “N-Rooks” để xếp N con xe vào bàn cờ NxN sao cho chúng không tấn công nhau.
84. Tìm tất cả các cách xếp các cặp đôi thành các cặp đôi phù hợp với nhau.
85. Tìm tất cả các hình đa giác convex có thể được tạo từ một danh sách điểm.
86. Tìm tất cả các cách xếp các chữ cái thành các từ với các ràng buộc về thứ tự.
87. Tìm tất cả các con đường từ một điểm đến một điểm khác trong một đồ thị có hướng.
88. Tìm tất cả các hình vuông con của một ma trận số.
89. Tìm tất cả các cách xếp một danh sách từ vựng thành các câu hợp lệ.
90. Tìm tất cả các cách xếp các mảng số nguyên thành các dãy tăng dần.
91. Tìm tất cả các dãy số nguyên liên tiếp có tổng là một số nguyên đã cho.
92. Tìm tất cả các dãy số con có tổng bằng một số nguyên đã cho.
93. Tìm tất cả các cặp số trong một mảng có tổng bằng một giá trị đã cho.
94. Tìm tất cả các cách xếp các thành phần của một danh sách thành các tập hợp con.
95. Tìm tất cả các định dạng chuỗi hợp lệ của biểu thức toán học.
96. Tìm tất cả các dãy con tăng dần dài nhất của một mảng số nguyên.
97. Tìm tất cả các định dạng chuỗi hợp lệ của các dấu ngoặc.
98. Tìm tất cả các dãy số con liên tiếp có tổng lớn nhất.
99. Tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên đã cho.
100. Tìm tất cả các cách xếp các phần tử của một tập hợp thành các tập hợp con không trùng lặp.