ปัญหาผลรวมเป้าหมายคือปัญหาการหาสับเซตที่ผลรวมขององค์ประกอบเท่ากับตัวเลขที่กำหนด วิธี Backtracking สร้างการเรียงสับเปลี่ยนทั้งหมดในกรณีแย่ที่สุด แต่โดยทั่วไปทำงานได้ดีกว่าวิธี recursive ต่อปัญหาสับเซตผลรวม
ให้สับเซต A ของจำนวนเต็มบวก n ตัวและค่า sum หาว่ามีสับเซตใดของเซตที่กำหนดที่ผลรวมขององค์ประกอบเท่ากับค่า sum ที่กำหนดหรือไม่
สมมติเรามีอาร์เรย์ [1,2,3] ผลลัพธ์จะเป็น "1,1,1,1", "1,1,2", "2,2", "13" จากผลลัพธ์ "31", "211", "121" สามารถตัดทิ้งได้
ตัวอย่าง
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication
{
public class BackTracking
{
public void Combinationsums(int[] array, int target)
{
List currentList = new List();
List> results = new List>();
int sum = 0;
int index = 0;
CombinationSum(array, target, currentList, results, sum, index);
foreach (var item in results)
{
StringBuilder s = new StringBuilder();
foreach (var item1 in item)
{
s.Append(item1.ToString());
}
Console.WriteLine(s);
s = null;
}
}
private void CombinationSum(int[] array, int target, List currentList, List> results, int sum, int index)
{
if (sum > target)
{
return;
}
else if (sum == target)
{
if (!results.Contains(currentList))
{
List newList = new List();
newList.AddRange(currentList);
results.Add(newList);
return;
}
}
else
{
for (int i = 0; i < array.Length; i++)
{
currentList.Add(array[i]);
CombinationSum(array, target, currentList, results, sum + array[i], i);
currentList.Remove(array[i]);
}
}
}
}
class Program
{
static void Main(string[] args)
{
BackTracking b = new BackTracking();
int[] arrs = { 1, 2, 3 };
b.Combinationsums(arrs, 4);
}
}
} ผลลัพธ์
1111 112 13 22
