สร้างรายการผลลัพธ์เพื่อจัดเก็บลำดับที่ถูกต้อง สร้างรายการปัจจุบันที่จะจัดเก็บลำดับปัจจุบันที่พบในเส้นทางของแผนผังการเรียกซ้ำ ฟังก์ชันย้อนรอยที่จะเข้าสู่การเรียกซ้ำจนกว่าเป้าหมายจะสำเร็จ มิฉะนั้น ควรย้อนย้อนไปยังเฟสก่อนหน้าเนื่องจากเป้าหมายมีค่าน้อยกว่า 0 ณ เวลาใด ๆ หากเป้าหมายกลายเป็น 0 ให้เพิ่มอาร์เรย์ตัวเลือกเข้ากับผลลัพธ์เป็น ค่าในอาร์เรย์ตัวเลือกจะต้องเป็นผลรวมของเป้าหมายที่กำหนด
หากไม่เป็นเช่นนั้น ให้เพิ่มองค์ประกอบในอาร์เรย์ตัวเลือกทีละรายการแล้วเลื่อนไปข้างหน้าซ้ำๆ
สมมติว่า ตัวเลขคือ 5 และ k คือ 2 ดังนั้นเราต้องรวมตัวเลขในขนาด 2 เข้าด้วยกันเป็น 5 ผลลัพธ์จะเป็น “1,4”,”2,3”
ตัวอย่าง
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
public class BackTracking{
public void UniqueCombinationSumOfExactKNumbers(int n, int k){
int[] array = new int[n];
for (int i = 1; i < n; i++){
array[i] = i;
}
List<int> currentList = new List<int>();
List<List<int>> output = new List<List<int>>();
UniqueCombinationSumOfExactKNumbers(array, n, k, 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 UniqueCombinationSumOfExactKNumbers(int[] array, int target, int countOfNumbers, int sum, int index, List<int> currentList, List<List<int>> output){
if (sum == target){
if (currentList.Count == countOfNumbers){
List<int> newList = new List<int>();
newList.AddRange(currentList);
output.Add(newList);
return;
}
}
else if (sum > target){
return;
}
else if (currentList.Count == countOfNumbers && sum != target){
return;
}
else{
for (int i = index; i < array.Length; i++){
currentList.Add(array[i]);
UniqueCombinationSumOfExactKNumbers(array, target, countOfNumbers, sum + array[i], i + 1, currentList, output);
currentList.Remove(array[i]);
}
}
}
}
class Program{
static void Main(string[] args){
BackTracking b = new BackTracking();
b.UniqueCombinationSumOfExactKNumbers(5, 2);
}
}
} ผลลัพธ์
14 23
