有多少组４个数加起来等于８的
５个
１１１５，　１２４１，２２２２，３２１２，３３１１

很急呀
大家帮帮忙

用动态规划可以解吧。就不知道最好的解法是什么。

class Combines
{
    Vector allCombines = new Vector();
    int[] oneCombine;
    
    public static void main(String[] args)
    {
        int n=4, m=8;
        Combines c = new Combines();
        
        int [][] result = c.getAllCombines(n, m);
        
        for (int i=0; i<result.length; ++i)
        {
            for (int j=0; j<n; ++j)
            {
               System.out.print(result[i][j]+" ");    
            }
            System.out.println();    
            
        }
    }
    
    
    public int[][]  getAllCombines(int n, int m)
    {
        int [][] result;
        
        oneCombine = new int [n];
        
        getOneCombine(0, n, m);
        
        result = new int [allCombines.size()][n];
        
        for (int i=0; i<allCombines.size(); ++i)
        {
            ArrayList item = (ArrayList)allCombines.get(i);
            for (int j=0; j<n; ++j)
            {
                result[i][j] = ((Integer)item.get(j)).intValue();
            }
        }
        
        return result;
    }
    
    boolean isCurCombineCorrect(int m)
    {
        int sum = 0;
        
        for (int i=0; i<oneCombine.length; ++i)
        {
            sum += oneCombine[i];
        }
        
        if (sum == m)
        {
            return true;
        }
        
        return false;
    }
    
    boolean isArraylogicalEqual(ArrayList aItem, ArrayList bItem)
    {
        int length = aItem.size();
        int i=0, j=0;
        
        for (i=0; i<length; ++i)
        {
            boolean equal = false;
            int aVal = ((Integer)aItem.get(i)).intValue();
            
            for (j=0; j<length; ++j)
            {
                if ( aVal == ((Integer)bItem.get(j)).intValue() )
                {
                    equal = true;
                }
            }
            
            if (equal == false)
            {
                return false;
            }
        }
        
        for (i=0; i<length; ++i)
        {
            boolean equal = false;
            int aVal = ((Integer)bItem.get(i)).intValue();
            
            for (j=0; j<length; ++j)
            {
                if ( aVal == ((Integer)aItem.get(j)).intValue() )
                {
                    equal = true;
                }
            }
            
            if (equal == false)
            {
                return false;
            }
        }
        
        return true;
    }
    
    boolean isCurCombineExist()
    {
        ArrayList curItem = new ArrayList();
        
        
        for (int k=0; k<oneCombine.length; ++k)
        {
             curItem.add(new Integer(oneCombine[k])) ;
        }
        
        
        for (int i=0; i<allCombines.size(); ++i)
        {
            ArrayList aItem = (ArrayList)allCombines.get(i);
            
            if (isArraylogicalEqual(aItem, curItem))
            {
                return true;
            }
        }
        
        return false;
    }
    
    void getOneCombine(int index, int n, int m)
    {
        if (index >= n)
        {
            //got one!
            if (isCurCombineCorrect(m))
            {
                if (isCurCombineExist() == false)
                {
                    ArrayList item = new ArrayList();
                    
                    for (int k=0; k<oneCombine.length; ++k)
                    {
                        item.add(new Integer(oneCombine[k]));
                    }
                    
                    allCombines.addElement(item);
                }
            }
            
            return;
        }
        
        //for (int i=0; i<n; ++i)
        {
            for (int j=1; j<=m-n+1; ++j)
            {
                oneCombine[index] = j;
                getOneCombine(index+1, n, m);
            }
        }
    }
    
}

Private Function com(m As Integer, n As Integer, a() As String) As Integer
    Dim b() As String, k As Integer, k1 As Integer, s As Integer
    Dim idx As Integer
    ReDim a(0)
    If m = n Then
        ReDim a(1)
        For i = 1 To n - 1
            a(1) = a(1) & "1 "
        Next i
        a(1) = a(1) & "1"
        com = 1
    ElseIf n = 1 Then
        ReDim a(1)
        a(1) = CStr(m)
        com = 1
    Else
        For i = 1 To m - n + 1
            k = com(m - i, n - 1, b)
            u = UBound(b)
            For j = 1 To u
                k1 = InStr(b(j), " ")
                If k1 = 0 Then
                    s = Val(b(j))
                Else
                    s = Val(Mid(b(j), 1, k1 - 1))
                End If
                If i >= s Then
                    idx = idx + 1
                    ReDim Preserve a(idx)
                    a(idx) = CStr(i) & " " & b(j)
                End If
            Next j
        Next i
        com = UBound(a)
    End If
End Function

实在没有找到更好的论坛,还是凑合来这里吧

   if(m>20||n>20||n<=0||m<=0)
   {

     return;
   }
   if(m<n)
   {
    return;
   }
   for(int i=1;i<=m-n+1;i++)
   {  
    cont[n-1]=i;
    cal(m-i,n-1,num);
   }
   if(n==1)
   {
      for(int u=0;u<num;u++)
     printf("%d ",cont[u]);
   printf("\n");
  }

}
void cal(int m,int n)
{
 cal(m,n,n);
}
void main()
{
  cal(15,5);

}

c语言精炼，呵呵

public class Composite {

 public void getComposite(int a, int b) {

  int n = 0;
  int y = 0;

  for (double i = Math.pow(10, b - 1); i < Math.pow(10, b) - 1; i++) {
   // 每个数
   String itos = String.valueOf((int) i);

   for (int j = 0; j < itos.length(); j++) {
    // 每个数字
    String temp = itos.substring(j, j+1);
    y = y + Integer.parseInt(temp);
   }
   if (y == a)
    n++;
   y = 0;
  }
  System.out.println(n);
 }

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new Composite().getComposite(8, 4);
 }

}

有了上面的公式,用栈来实现遍历.

/*

while((m-n+1)>0)
 {
  Node.value = m-n+1;
  Node.floor = 1;
  Stack.push(Node);
  (m-n+1)--;
 }
while(棧不为空){//构造下一层的元素，并放入棧中
 tmpNode = stack.pop();
 curfloor = tmpNode.floor+1;
 curValue = curValue +tmpNode.value;
 tmpTrace[curfloor -1 ] =curValue;
 while(m-curValue-n+curfloor > 0 && curfloor <n)
 {
  int i = m-curValue-n+curfloor ;
  Node.value = i;
  Node.floor = curfloor;
  stack.push(Node);
  (m-curValue-n+curfloor) --;
 }
 curfloor = tmpNode.floor;
 if (curfloor = n-1)
 {
  tmpTrace[curfloor+1]= m-curValue;
  if (compare(tmpTrace,Trace))//如果路径没有被遍历过，则放入到Trace中
  {
   把tmpTrace放入Trace中；//Trace用来保存遍历到的路径
  }
 }
 curValue = curValue - tmpNode.value;//把curValue恢复到没有修改以前，以便下个元素遍历
}
*/

int main(])
{
 unsigned long it, minit, maxit;
 int n, m;
 int s;
 int r;
 int count = 0;

 scanf("%d, %d", &n, &m);

 maxit = (unsigned long)pow(10.0, n);
 minit = (unsigned long)pow(10.0, n-1);

 for ( it = minit; it < maxit; it++ )
 {
  r = it;
  s = 0;
  while(r>0)
  {
   s = s + (r % 10);
   r = r / 10;
  }
 
  if ( s == m )
  {
   printf("%8ld", it);
   count++;
  }
 }

 printf("\nCount = %d", count);

 getch();

 return 0;
}

解决方法大致可以分为以下两种思路：
1.简单的循环测试。这种方法的时间复杂度是O(m^n)，注：m^n表示m的n次方。这种方法的代表是：14楼，15楼，23楼。其中，15楼采用递归实现，但在时间复杂度上跟用非递归实现是一样的。

2.将结果的数串以一个整体（大整数）考虑，先设置好循环的范围，然后再在该范围内测试这些大整数的各个数位取出来相加，看结果是否是正确解。例如m=8,n=4，意思是找出4个数字相加的结果是8的全部组合。用方法2的思想，他的处理思路是，4个数字如果组成一个大整数的话，范围是1000-9999之间，即10^3到10^4之间，所以原题可以考虑成在1000-9999之间找出各个数位加起来是8的全部数字。取各个数位的时候采用了模10的方法。
这种方法只有一个循环，但是该循环的范围比较大，而且中间在取各个数位的时候也有一个常数阶的循环，这种方法的时间复杂可表示为O(n*(10^n - 10^(n-1)))。这种方法的代表是：17楼，20楼。前者是java版的，后者是C语言版的。

可以证明两算法的时间复杂度满足如下关系：
当m<=10时，m^n < n*(10^n - 10^(n-1))；
当m > 10时，m^n > n*(10^n - 10^(n-1))。

在分析过程中略去了有些朋友的解法，在此表示歉意。另外，由于个人水品有限，在分析过程中如果有错误的地方还望大家指正。

int f(int m,int n)
{
 int i;
 int s=0;
 int stop;
 if (m==n)
  return 1;
 stop=m-n>n?n:m-n;
 for (i=1;i<=stop;++i)
  s+=f(m-n,i);
 return s;
}

int main()
{
 int m,n,result;
 scanf("%d %d",&m,&n);
 result=f(m,n);
 printf("\nThe answer is:%d\n",result);
 return 0;
}

f(m,n)=sum{[i=1 to min(m-n,n)] f(m-n,i)}
这种题数学方法是最简单的。

还可以用减枝法来减少计算量.

汗，枚举，人家要的是DP解。。。

要存储 子问题的 解.

不错

由于有文字不好写“n次方”“累加，累乘”原谅。
可见<<组合数学第三版>>Brualdi,144页，188页。
如果按14楼写法，n的拆分数有写：n=a1*n+a2*(n-1)......an*1;n次for,复杂度O(n，n次方)

dp[n][n]=1;

如此DP

时间O(n*n)

由于 8 <= 20. 所以要求均为正数时就是4-1=3个1，8-4=4个0的全组合。用prolog 很容易生成。

（一般x1+x2+x3+ ...+ xn = r, 要求xi >=0时就是组合数C(n+r-1,r)）

在有上界限制时，比如 m >= xi >=0，而m < r，则可以用mathematica和生成多项式，
(1+x1+x1^2+...+x1^m)(1+x2+...)...(1+xn+...), 最后截取所有指数和为r的项且不计变元的不同即可。

}