ปัญหาผลรวมเป้าหมายคือปัญหาในการหาเซตย่อยโดยให้ผลรวมขององค์ประกอบเท่ากับจำนวนที่กำหนด วิธีการย้อนรอยสร้างการเปลี่ยนแปลงทั้งหมดในกรณีที่เลวร้ายที่สุด แต่โดยทั่วไปแล้ว ทำได้ดีกว่าวิธีการแบบเรียกซ้ำสำหรับปัญหาผลรวมเซตย่อย
เซตย่อย A ของจำนวนเต็มบวก n จำนวนและให้ผลรวมของค่า หาว่ามีซับเซ็ตของเซตที่ระบุหรือไม่ ผลรวมขององค์ประกอบที่มีเท่ากับค่าของผลรวมที่กำหนด
สมมติว่าเรามีอาร์เรย์ [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<int> currentList = new List<int>();
List<List<int>> results = new List<List<int>>();
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<int> currentList, List<List<int>> results, int sum, int index){
if (sum > target){
return;
}
else if (sum == target){
if (!results.Contains(currentList)){
List<int> newList = new List<int>();
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
