สร้างรายการผลลัพธ์เพื่อเก็บลำดับที่ถูกต้อง สร้างรายการปัจจุบันที่จะเก็บลำดับปัจจุบันที่พบในเส้นทางของต้นไม้ recursion ฟังก์ชัน backtrack ที่จะเข้าสู่ recursion จนกว่าจะบรรลุเป้าหมาย มิฉะนั้นจะ backtrack กลับไปขั้นตอนก่อนหน้าเมื่อ target น้อยกว่า 0 หาก target กลายเป็น 0 ให้เพิ่มอาร์เรย์ผู้สมัครเข้าไปในผลลัพธ์ เนื่องจากค่าในอาร์เรย์ผู้สมัครต้องรวมกันได้เท่ากับ target ที่กำหนด
หากไม่ใช่กรณีดังกล่าว ให้นำองค์ประกอบในอาร์เรย์ผู้สมัครมาเพิ่มทีละตัวและเรียก recursion ต่อไป
เช่น ตัวเลขคือ 5 เราต้องหาตัวเลขที่รวมกันได้ 5 ผลลัพธ์จะเป็น "1,4", "2,3", 5 จากผลลัพธ์ 014, 023 และ 05 สามารถตัดทิ้งได้
ตัวอย่าง
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 currentList = new List();
List> output = new List>();
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 currentList, List> output)
{
if (sum == target)
{
List newList = new List();
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);
}
}
} ผลลัพธ์
14 23 05
