Cách tìm tổng mục tiêu từ mảng cho trước bằng backtracking C#

Bài toán tổng mục tiêu là tìm tập con sao cho tổng các phần tử bằng một số cho trước. Cách tiếp cận backtracking tạo ra tất cả hoán vị trong trường hợp xấu nhất nhưng nói chung hiệu quả hơn đệ quy thuần túy cho bài toán tập con tổng.

Cho tập A n số nguyên dương và giá trị sum, tìm xem có tồn tại tập con nào của tập cho trước mà tổng các phần tử bằng sum cho trước không.

Ví dụ mảng [1,2,3], target=4. Kết quả: "1,1,1,1", "1,1,2", "2,2", "1,3". Từ đầu ra "3,1", "2,1,1", "1,2,1" có thể loại bỏ (trùng lặp theo thứ tự).

Ví dụ

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);
        }
    }
}

Kết quả

1111 112 13 22