Tạo danh sách đầu ra để lưu trữ các trình tự hợp lệ, tạo danh sách hiện tại sẽ lưu trữ trình tự hiện tại được tìm thấy trong đường dẫn của cây đệ quy. Một hàm backtrack sẽ đi vào đệ quy cho đến khi đạt được mục tiêu, nếu không, nó sẽ quay lại giai đoạn trước khi mục tiêu trở nên nhỏ hơn 0. Tại bất kỳ thời điểm nào, nếu mục tiêu trở thành 0 thì hãy thêm mảng ứng viên vào kết quả như các giá trị trong mảng ứng viên phải được tổng hợp với mục tiêu đã cho.
Nếu đó không phải là trường hợp thì hãy thêm lần lượt các phần tử trong mảng ứng viên và tiếp tục đệ quy.
Giả sử, số là 5, vì vậy chúng ta cần tìm các số tạo thành 5. Kết quả đầu ra sẽ là “1,4”, “2,3”, 5. Từ Đầu ra 014, .023 và 05 có thể bị loại bỏ
Ví dụ
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
public class BackTracking{
public void UniqueCombinationOfNumbersCorrespondsToSum(int n){
int[] array = new int[n + 1];
for (int i = 1; i <= n; i++){
array[i] = i;}
List<int> currentList = new List<int>();
List<List<int>> output = new List<List<int>>();
UniqueCombinationSum(array, n, 0, 0, currentList, output);
foreach (var item in output){
StringBuilder s = new StringBuilder();
foreach (var item1 in item){
s.Append(item1.ToString());
}
Console.WriteLine(s);
s = null;
}
}
private void UniqueCombinationSum(int[] array, int target, int sum, int index, List<int> currentList, List<List<int>> output){
if (sum == target){
List<int> newList = new List<int>();
newList.AddRange(currentList);
output.Add(newList);
return;
}
else if (sum > target){
return;
}
else{
for (int i = index; i < array.Length; i++){
currentList.Add(array[i]);
UniqueCombinationSum(array, target, sum + array[i], i + 1, currentList, output);
currentList.Remove(array[i]);
}
}
}
}
class Program{
static void Main(string[] args){
BackTracking b = new BackTracking();
b.UniqueCombinationOfNumbersCorrespondsToSum(5);
}
}
}
} Đầu ra
14 23 05