打印总和为特定值的所有子集

Question

一段时间以来，我一直在努力寻找总和为特定值的数组的所有元素 ^{（包括不连续的）}：

using System;

namespace ProgrammingBasics 
{
    class Exercise
    {
        static void Main()
        {
            PrintArray(arr);
            SubarrayWithSum();
        }
        //--------------------------------------------------------------------

        /*
            Data members.

        */
        // targer array
        static int[] arr = { 2, 1, 2, 4, 3, 5, 2, 6 };
        // target sum
        static int sum = 14;

        //--------------------------------------------------------------------

        /*
            Method: IsSubarrayWithSum(arr, sum);

            It returns a bool value that indicates
            whether there is a subarray within arr
            with elements that sum up to specific value.
        */
        static void SubarrayWithSum()
        {
            int depth = 0;
            int startIndex = 0;
            int endIndex = 1;

            CheckAllCombinations(new int[arr.Length], startIndex, endIndex, depth);
        }
        //--------------------------------------------------------------------

        /*
            Method: CheckAllCombinations(subarray, sum);

        */
        static void CheckAllCombinations(int[] subarray, int startIndex, int endIndex, int depth)
        {
            if (depth >= arr.Length)
            {
                return;
            }
            //Console.ReadKey();
            for (int i = startIndex; i < endIndex; i++)
            {
                subarray[i] = arr[i];
                //Console.WriteLine("startIndex = {0}, depth = {1}, i = {2}", startIndex, depth, i);
                if (IsWantedSum(subarray))
                {
                    Console.Write("S = {0} -> yes", sum);
                    PrintSubArray(subarray);
                }
                //PrintArray(subarray);
                //Console.ReadKey();
                CheckAllCombinations(new int [arr.Length], startIndex += 1, endIndex = (endIndex < arr.Length)? endIndex + 1 : endIndex, depth += 1);
            }
        }
        //--------------------------------------------------------------------

        /*
            Method: IsWantedSum(int[] arr)

        */
        static bool IsWantedSum(int[] arr)
        {
            int currentSum = 0;

            for (int i = 0; i < arr.Length; i++)
            { 
                currentSum += arr[i];
            }

            if (currentSum == sum)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        //--------------------------------------------------------------------
        /*
            Method: PrintArray();

        */
        static void PrintArray(int[] subarray)
        {
            Console.Write("{");
            for (int i = 0; i < subarray.Length; i++)
            {
                Console.Write(subarray[i]);
                if (i < subarray.Length -1) Console.Write(", ");
            }
            Console.WriteLine("}");
        }

        //--------------------------------------------------------------------
        /*
            Method: PrintSubArray();

        */
        static void PrintSubArray(int[] subarray)
        {
            Console.Write("(");
            for (int i = 0; i < subarray.Length; i++)
            {
                if (subarray[i] != 0)Console.Write(subarray[i]);
                if (subarray[i] != 0 && i < subarray.Length - 1) Console.Write(" + ");
            }
            Console.WriteLine(" = {0})", sum);
        }
    }
}

我得到了部分正确的结果：

{2, 1, 2, 4, 3, 5, 2, 6}
S = 14 -> yes(4 + 3 + 5 + 2 + = 14)
S = 14 -> yes(2 + 4 + 3 + 5 + = 14)
S = 14 -> yes(4 + 3 + 5 + 2 + = 14)
S = 14 -> yes(4 + 3 + 5 + 2 + = 14)
S = 14 -> yes(2 + 4 + 3 + 5 + = 14)
S = 14 -> yes(4 + 3 + 5 + 2 + = 14)

具有重复和缺失的非连续元素的子数组，例如：

yes (1 + 2 + 5 + 6 = 14)

有人可以给我一些关于我算法问题的提示，并可能建议更正/新实现吗？

Answer 1

这里有一个简单的组合方法。可能有更好的方法来存储它们（我正在考虑使用字典来编码您已经拥有的所有子金额）。归根结底，如果你想考虑非连续元素，你将不得不获得在这种情况下可能的子数组，而不仅仅是查看连续的选择。组合算法归功于 ojlovecd here .

    class Exercise
    {
        static void Main()
        {
            PrintArray(arr);
            // SubarrayWithSum();


            var result = GetCombination(arr);

            foreach(var list in result)
            {
                var total = list.Sum();
                if (total == sum)
                    PrintArray(list);
            }
        }
        static List<int> arr = new List<int> { 2, 1, 2, 4, 3, 5, 2, 6 };
        static int sum = 14;

        static List<List<int>> GetCombination(List<int> list)
        {
            var result = new List<List<int>>();
            result.Add(new List<int>());
            double count = Math.Pow(2, list.Count);
            for (int i = 1; i <= count - 1; i++)
            {
                string str = Convert.ToString(i, 2).PadLeft(list.Count, '0');
                for (int j = 0; j < str.Length; j++)
                {
                    if (str[j] == '1')
                    {
                        result[i - 1].Add(list[j]);
                    }
                }
                result.Add(new List<int>());
            }
            return result;
        }

        static void PrintArray(List<int> subarray)
        {
            Console.Write("{");
            for (int i = 0; i < subarray.Count; i++)
            {
                Console.Write(subarray[i]);
                if (i < subarray.Count - 1) Console.Write(", ");
            }
            Console.WriteLine("}");
        }
    }

Answer 2

我认为出现重复是因为您在添加的数组中有零。查看运行速度更快的更新代码。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace ProgrammingBasics
{
    class Exercise
    {
        static void Main()
        {
            PrintArray(arr);
            SubarrayWithSum();
        }
        //--------------------------------------------------------------------

        /*
            Data members.

        */
        // targer array
        static int[] arr = { 2, 1, 2, 4, 3, 5, 2, 6 };
        // target sum
        static int sum = 14;

        //--------------------------------------------------------------------

        /*
            Method: IsSubarrayWithSum(arr, sum);

            It returns a bool value that indicates
            whether there is a subarray within arr
            with elements that sum up to specific value.
        */
        static void SubarrayWithSum()
        {
            int depth = 0;
            int endIndex = arr.Length - 1;

            CheckAllCombinations(new int[arr.Length], depth);
        }
        //--------------------------------------------------------------------

        /*
            Method: CheckAllCombinations(subarray, sum);

        */
        static void CheckAllCombinations(int[] subarray, int depth)
        {
            //Console.ReadKey();
            for (int i = depth; i < arr.Length; i++)
            {
                subarray[depth] = arr[i];
                Console.WriteLine("depth = {0}, i = {1}, array = '{2}'  ", depth, i, string.Join(",", subarray.Select(x => x.ToString()).ToArray()));
                int currentSum = subarray.Take(depth + 1).Sum();
                if (currentSum == sum)
                {
                    Console.Write("S = {0} -> yes : ", sum);
                    Console.WriteLine(string.Join(",", subarray.Take(depth + 1)));
                }
                //PrintArray(subarray);
                //Console.ReadKey();
                if (currentSum < sum)
                {
                    CheckAllCombinations(subarray, depth + 1);
                }
            }
        }
        //--------------------------------------------------------------------

        /*
            Method: IsWantedSum(int[] arr)

        */

        //--------------------------------------------------------------------
        /*
            Method: PrintArray();

        */
        static void PrintArray(int[] subarray)
        {
            Console.Write("{");
            for (int i = 0; i < subarray.Length; i++)
            {
                Console.Write(subarray[i]);
                if (i < subarray.Length - 1) Console.Write(", ");
            }
            Console.WriteLine("}");
        }

        //--------------------------------------------------------------------
        /*
            Method: PrintSubArray();

        */
        static void PrintSubArray(int[] subarray)
        {
            Console.Write("(");
            for (int i = 0; i < subarray.Length; i++)
            {
                if (subarray[i] != 0) Console.Write(subarray[i]);
                if (subarray[i] != 0 && i < subarray.Length - 1) Console.Write(" + ");
            }
            Console.WriteLine(" = {0})", sum);
        }
    }
}

Answer 3

好的，这里是一个小小的尝试，简要描述我为理解问题¹ 并实施基本解决方案所经历的信息。

It turns out that The Subset Sum Problem is considered a special case of the Knapsack Problem in which we are searching to maximize profit while keeping value called weight under specific capacity, but in our case the profit and weight associated with each value are identical.

“背包问题”- Keller、Pferschy、Pisinger 中描述了多种出色的解决方案，但是，目前这是我可以实施和理解的最简单的解决方案，不考虑复杂性和/或功效，看起来像这样：

    //--------------------------------------------------------------------

    /*
        Method: FindSubArray();

        Base case: - if current sum == targer sum: print current elements.
                   - if index == arr.Length: terminate search.

        Recursive step: 
                   - do not/select element with index and do not/update the current sum; recursive call with updated current sum and index.
    */
    static void FindSubArray(int index, int currentSum, bool[] subArray)
    {
        // base case
        if (currentSum == targetSum)
        {
            PrintSubArray(subArray);
        }
        else if (index == arr.Length)
        {
            return;
        }
        else
        {
            // recursive calls
            subArray[index] = true;
            currentSum += arr[index];
            FindSubArray(index + 1, currentSum, subArray);

            currentSum -= arr[index]; // restore previous value of the sum signifying: element not selected
            subArray[index] = false;
            FindSubArray(index + 1, currentSum, subArray);
        }
    }

其中 PrintSubArray(subArray); 打印 subArray 中标记为 true 的 arr 的所有元素。

输出：

{2, 1, 2, 4, 3, 5, 2, 6}
S = 14 -> yes (2 + 1 + 2 + 4 + 3 + 2 + = 14)
S = 14 -> yes (2 + 1 + 2 + 4 + 5 + = 14)
S = 14 -> yes (2 + 1 + 2 + 3 + 6 = 14)
S = 14 -> yes (2 + 1 + 4 + 5 + 2 + = 14)
S = 14 -> yes (2 + 1 + 3 + 2 + 6 = 14)
S = 14 -> yes (2 + 1 + 5 + 6 = 14)
S = 14 -> yes (2 + 2 + 4 + 6 = 14)
S = 14 -> yes (2 + 2 + 3 + 5 + 2 + = 14)
S = 14 -> yes (2 + 4 + 3 + 5 + = 14)
S = 14 -> yes (2 + 4 + 2 + 6 = 14)
S = 14 -> yes (1 + 2 + 4 + 5 + 2 + = 14)
S = 14 -> yes (1 + 2 + 3 + 2 + 6 = 14)
S = 14 -> yes (1 + 2 + 5 + 6 = 14)
S = 14 -> yes (1 + 4 + 3 + 6 = 14)
S = 14 -> yes (1 + 5 + 2 + 6 = 14)
S = 14 -> yes (2 + 4 + 3 + 5 + = 14)
S = 14 -> yes (2 + 4 + 2 + 6 = 14)
S = 14 -> yes (4 + 3 + 5 + 2 + = 14)
S = 14 -> yes (3 + 5 + 6 = 14)

我正在阅读的书将问题简单地描述为：“查找是否存在元素总和为特定值的子数组”。

打印总和为特定值的所有子集

Print all subsets that sum up to specific value

c#

arrays

algorithm

recursion

subset-sum