已知和，求加数

已知和，求加数。如有四个数1 2 2 3，要从中得到相加的结果等于4是由哪几个数相加而得来的，且有几种计算结果
--------------------编程问答-------------------- 问一下幼儿园阿姨 --------------------编程问答-------------------- 最奔的方法是穷举，这总会吧 --------------------编程问答-------------------- 给一个C#的版本

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace ConsoleApplication1

{    

    class Program

    {

        static void Main(string[] args)

        {

            var result = OutPut(16, new int[] { 1, 2, 4 }, new List<int>());

            foreach (var item in result)

                Console.WriteLine(string.Join(",", item.Select(x => x.ToString())));

        }

 

        /// <summary>

        /// 求一个数 有些数的之和组成的排列

        /// </summary>

        /// <param name="sum">和数</param>

        /// <param name="array">构成的数字</param>

        /// <returns>返回能够组成的一个集合</returns>

        public static IEnumerable<List<int>> OutPut(int sum, int[] array, IEnumerable<int> seed)

        {

            if (seed.Sum() == sum)

                yield return seed.ToList();

            else

                foreach (var item in array.Where(x => x >= seed.LastOrDefault()).Select(x => seed.Concat(new int[] { x })).Where(x => x.Sum() <= sum).SelectMany(x => OutPut(sum, array, x)))

                    yield return item;

 

        }

    }

}

--------------------编程问答-------------------- http://bbs.csdn.net/topics/390360329

至于VB嘛，反正很多人高喊“语言都一样，重要的是思路”，你就请这些人帮你改改吧。 --------------------编程问答-------------------- 子集合加总问题
集合中的元素有个数限制哦
用Linq还是避免不了指数复杂度滴 --------------------编程问答-------------------- --------------------编程问答--------------------

引用 6 楼 Tiger_Zhao 的回复:

Option Explicit



Private lCount As Long

Private aValue() As Long

Private aUsed() As Boolean



Sub Main()

    lCount = 4

    ReDim aValue(1 To lCount)

    aValue(1) = 1

    aValue(2) = 2

    aValue(3) = 2

    aValue(4) = 3

    ReDim aUsed(1 To lCount)

    

    f 1, 4

End Sub



Sub f(ByVal Index As Long, ByVal Sum As Long)

    Dim i As Long

    

    For i = Index To lCount

        Select Case Sgn(aValue(i) - Sum)

            Case 0 'aValue(i) = Sum

                aUsed(i) = True

                Output

            Case -1 'aValue(i) < Sum

                aUsed(i) = True

                f i + 1, Sum - aValue(i)

        End Select

        aUsed(i) = False

    Next

End Sub



Sub Output()

    Dim i As Long

    

    For i = 1 To lCount

        If aUsed(i) Then Debug.Print "+" & aValue(i);

    Next

    Debug.Print

End Sub

也不能说你的代码是错的，得看怎么理解“由哪几个数相加而得来的”。不过一般的理解是可以重复。
比如 1+1+2=4 或者 1+1+1+1=4。 --------------------编程问答--------------------

引用 7 楼 caozhy 的回复:

也不能说你的代码是错的，得看怎么理解“由哪几个数相加而得来的”。不过一般的理解是可以重复。
比如 1+1+2=4 或者 1+1+1+1=4。

哪里看出能重复使用的？
aUsed() 只能标记用或不用，想表示用多次是不可能的。 --------------------编程问答-------------------- 来个非递归的版本，基于Tiger_Zhao

Option Explicit

 

Private lCount As Long

Private aValue() As Long

Private aUsed() As Long

 

Sub Main()

    lCount = 4

    ReDim aValue(1 To lCount)

    aValue(1) = 1

    aValue(2) = 2

    aValue(3) = 2

    aValue(4) = 3

    ReDim aUsed(0 To lCount)

     

    f 4

End Sub

 

Sub f(ByVal Sum As Long)

    Dim i As Long, j As Long

    Dim s As Long

    

    Do Until aUsed(0) = 1

        s = 0

        

        For i = lCount To 1 Step -1

            s = s + aUsed(i) * aValue(i)

            

            If s > Sum Then

                Exit For

            ElseIf s = Sum Then

                Output

            End If

        Next i

        

        aUsed(lCount) = aUsed(lCount) + 1

        

        For j = lCount To 1 Step -1

          If aUsed(j) > 1 Then

            aUsed(j) = 0

            aUsed(j - 1) = aUsed(j - 1) + 1

          Else

            Exit For

          End If

        Next j

    Loop

End Sub

 

Sub Output()

    Dim i As Long

     

    For i = 1 To lCount

        If aUsed(i) = 1 Then Debug.Print "+" & aValue(i);

    Next

    Debug.Print

End Sub

--------------------编程问答-------------------- 有Bug。。。

Option Explicit

 

Private lCount As Long

Private aValue() As Long

Private aUsed() As Long

 

Sub Main()

    lCount = 4

    ReDim aValue(1 To lCount)

    aValue(1) = 1

    aValue(2) = 2

    aValue(3) = 2

    aValue(4) = 3

    ReDim aUsed(0 To lCount)

     

    f 4

End Sub

 

Sub f(ByVal Sum As Long)

    Dim i As Long, j As Long

    Dim s As Long

    

    Do Until aUsed(0) = 1

        s = 0

        

        For i = lCount To 1 Step -1

            s = s + aUsed(i) * aValue(i)

            

            If s > Sum Then Exit For

        Next i

        If s = Sum Then Output

        

        aUsed(lCount) = aUsed(lCount) + 1

        For j = lCount To 1 Step -1

          If aUsed(j) > 1 Then

            aUsed(j) = 0

            aUsed(j - 1) = aUsed(j - 1) + 1

          Else

            Exit For

          End If

        Next j

    Loop

End Sub

 

Sub Output()

    Dim i As Long

     

    For i = 1 To lCount

        If aUsed(i) = 1 Then Debug.Print "+" & aValue(i);

    Next

    Debug.Print

End Sub

--------------------编程问答-------------------- 来学习一下多个版本

补充：VB ,  基础类