满足条件的排列组合

先排序。然后从头开始一个个加，到100刚返回一个序列，大于100时continue;从第二个再开始加。

这算法不好写,如果有n个数的话,要从组合C1算到Cn,每个都遍历一次

子集求和问题我给你代码用的是非递归的回溯法
package com.haojia.algorithm;import java.util.Random;/**
* 子集求和非递归回溯效率高
*
* @author July
*
*/
public class SubSum { // 计算
public static void compute(int[] data, int sum) {
boolean[] state = new boolean[data.length];
int p = 0;
int temp = 0;
int count = 0; while (true) {
// 累加开始
while (p != data.length) {
if (!state[p]) {
state[p] = true;
temp += data[p];
if (temp == sum) {
count++;
print(data, sum, state);
}
if (temp > sum) {
state[p] = false;
temp -= data[p];
}
}
p++;
}
// 累加结束 // 回溯开始
while (state[p - 1]) {
state[p - 1] = false;
temp -= data[p - 1];
p--;
if (p == 0) {
System.out.println(count + "种方法");
return;
}
} while (!state[p - 1]) {
p--;
if (p == 0) {
System.out.println(count + "种方法");
return;
}
} state[p - 1] = false;
temp -= data[p - 1];
// 回溯结束
}
} // 格式化打印
public static void print(int[] data, int sum, boolean[] state) {
StringBuffer s = new StringBuffer();
for (int i = 0; i < data.length; i++) {
if (state[i]) {
s.append(data[i]);
s.append("+");
}
}
System.out.println(s.substring(0, s.length() - 1) + "=" + sum);
} public static void main(String[] args) {
Random r = new Random();
int[] data = new int[20];
for (int i = 0; i < data.length; i++) {
data[i] = r.nextInt(100);
}
compute(data, 100);
}
}

上面这个代码写法比较经典的而且效率比较高希望你能仔细看一下
其中最关键的思路是用一个boolean数组来标记随机数组里的数是否被加过
之后便可以通过考察boolean数组的状态进行回溯

测试了14L的方法结果又误。
如果数组int[] data = new int[]{5,5,5,5,20,20,20,20,10,10,10,5,5,10,10,20,20,10,10,5};
计算结果是65386种，显然不是我们所要求的组合。：另LS的同志些都不运行下结果瞎起哄。回帖不是打个“顶”就OK了，还不如不看呢。

能说明你给的是下面哪种情况吗：
1.给的随机数不能重复的在一种情况下出现（#14符合你的要求，不过代码有误需要修改，我建议你们不要只是把算法发上来，真正的测试运行下）
2.可以重复的出现，比如100%n==0，那么可以是一些n在组成一种组合，如{20，20，20，20，20}（#14代码和算法就不对了）
3.在2中还可以是x个n和y个m组成一个组合，如{20，20，20，20，5，5，5，5}它们相加也是100.请lz说明是以上哪种情况，然后我可以用比较复杂的算法解决（时间复杂度比较高）

14楼的我运行了，但是没有重复的情况，结果倒是没什么问题，首先感谢下14楼，但是我想要的是允许有重复的，26楼的说的符合我的要求2.可以重复的出现，比如100%n==0，那么可以是一些n在组成一种组合，如{20，20，20，20，20}（#14代码和算法就不对了）
3.在2中还可以是x个n和y个m组成一个组合，如{20，20，20，20，5，5，5，5}它们相加也是100. 烦请给出代码，谢谢大虾了，在此也谢谢各楼的关注，希望继续帮忙啊

不难，就是做一个组合算法：把所有的组合可能都求出来，然后计算该组合中是否可能加成100。这样分解为两步：
1.求出所有组合可能。这不难，我已有代码。（当然如果该组合中的数直接相加已经大于100先行舍去。）
2.求出该组合中是否可以相加得到100。这就是个背包问题，只是限制背包不能剩余而已。只要从最小的开始试就行了。这步用一下递归。很抱歉的是，我是从C++区转过来的，Java是初学者，没有能力给你写出代码。如果LZ需要C++的代码请给我留言。

kfdjhdjkhfd f dkfu

package cxz.math;import java.util.Calendar;public class Cal {
  int[] data = { 5, 5, 5, 5, 20, 20, 20, 20, 10, 10, 10, 5, 5, 10, 10, 20, 20, 10, 10, 5 };
  int total = 100;
  /////////////////
  int nt = data.length;
  int[] s = new int[nt];
  int m[] = { 1, 0 };
  int fm = 0;
  int no = 0;  public static void main(String[] args) {
    Calendar cstart = Calendar.getInstance();
    Cal g = new Cal();
    g.cal();
    Calendar cend = Calendar.getInstance();
    System.out.println("花费时间" + (cend.getTimeInMillis() - cstart.getTimeInMillis()) / 1000.0 + "秒");
  }  public void cal() {
    fm = 0;
    f(0);
  }  private void f(int n) {
    if (n == nt) {
      return;
    }
    for (int i = 0; i < m.length; i++) {
      s[n] = m[i];
      if (m[i] == 1) {
        fm += data[n];
        if (fm == total) {
          no++;
          show();
        }
      }
      if (fm < total)
        f(n + 1);
      if (m[i] == 1) {
        fm -= data[n];
      }
    }
  }  void show() {
    StringBuffer buf = new StringBuffer();
    for (int L = 0; L < data.length; L++)
      buf.append((s[L] == 1 ? (data[L] + " ") : ""));
    System.out.println(no + ":" + buf.toString());
  }
}

int flag[]={0};
int num[]={随机数};void func(int i)
{
if(i>=数组大小)
{
//检查标志位为1的num相加是否满足要求。
return;
}flag[i]=0;
func(i+1);
flag[i]=1;
func(i+1);
}结帖率那么低，真不想回答你的问题。

先排序。然后从头开始一个个加，到100刚返回一个序列，大于100时continue;从第二个再开始加。

提供给大家一个新的思路。这个问题的确是比较麻烦，但是我认为第一步应该是这个范围固定下：
1.首先去掉大于100 的元素。得到一个新数组；
2.剔除数组中重复的数据，因为本身可以重复取，所以去掉无所谓。
3.然后排序，则数据中的元素个数<=100个，这样数组的长度就比较小的。解决起来应该就方便点至于问题的本质，我正在考虑中。14L的代码没有注释和说明，有点难懂啊。。很有意思，再好好想想看。

想了一下，用递归实现好像比较快。我的思路如下，没有运行啊。用记事本写的，现在手上没有工具，过2天再上机测试看看。用的C#语言
1.去掉 >100 的元素。得到一个新组，并除去数组中重复的数据，因为本身可以重复取，所以去掉无所谓。然后排序，则数据中的元素个数<=100；
原始数组为 OrigData,N为所求的和值
设元素为1-->N；HashTable ht ;存储找到的序列组int[] Prepare(int[] OrigData,int N) //预处理方法,得到处理后的数组，就是步骤1中的，比较简单HashTable GetAllCombination(int[] OrigData,int N)
{
    HashTable ht = new HashTable() ;
    if(N<=0)
         return null ;//返回为空，说明需要找的为0，也就是已经满足条件
    int[] Randoms = PrePare(OrigData,N) ;//预处理原始数据
    for(int i=0;i<Randoms.Length;i--)
    {
        int cutValue = Randoms[i] ;//当前数组的值
    //获取其除数，因为需要重复，而最大的重复量就是其倍数，可以对除数依次递减，以此来获得重复的数
       int n1=N/cutValue ;
       int temp = n1*cutValue ;
      // if(temp==N) //说明能够整除
            //将当前值重复n1次添加到HashTable,作为一条符合条件的记录
       for(int j=n1 ; j>0;j--)
       {
           string cutCombination= GetNcombination(cutValue,j);
           HashTable tempHt=GetAllCombination(Randoms,N-j*cutValue) ;
           if(tempHt==null)
              // 将当前值cutValue 重复n1次添加到HashTable,作为一条符合条件的记录
              ht.Add(cutCombination);
           else //遍历hash表，将其添加到这之后并作为一条记录
                //合并并添加记录
                foreach(var a in tempHt)
                     ht.Add(cutCombination+var) ;
       }
    }

}//将值cutValue去times次组合的结果
string GetNcombination(int cutValue ,int times)
{
      string str="";
      for(int i=0;i<times;i++)
      {str+=(cutValue.ToString()+",") ;}
       return str ;
}

分析了一下，我上面说的方法有的不可行，因为递归调用速度会很慢，要重复计算很多东西。至于14楼的代码以及50楼的代码，没有分析和测试，哪位运行看看。
我的思路是采用迭代计算。因为每一个数都可以看成是2个数的和，如果一个数能分解，则把可分解的数代入，得到一个新的组合。从1开始运行，每一步都要搜索所有的组合。
首先的第一步还是进行下列操作：
1.去掉 >N 的元素。得到一个新组，并除去数组中重复的数据，因为本身可以重复取，所以去掉无所谓。然后排序，则数据中的元素个数 <=N ；
根据上面兄弟的测试结果，采用这组数据：
int[] data = new int[]{5,5,5,5,20,20,20,20,10,10,10,5,5,10,10,20,20,10,10,5};
我的程序运行的结果只有36种，而14楼的方法计算结果是65386种。差别这么大，大家手动计算一下就可以了，因为只包括5，10，20这3个元素，可以重复取，这个问题就类似于100元钱，用现有的货币组合，共有多少种。如果只有5，10，20这3种货币，怎么可能组合成那么多？我把计算出的36种结果列出来，大家看看：5,5,5,5,5,5,10,20,20,20
5,5,5,5,5,5,5,5,5,5,10,20,20
5,5,5,5,20,20,20,20
10,10,10,10,10,10,20,20
5,5,5,5,5,5,5,5,5,5,10,10,10,10,10
5,5,5,5,5,5,5,5,10,10,10,10,10,10
5,5,5,5,5,5,5,5,10,10,20,20
20,20,20,20,20
10,10,10,10,20,20,20
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,10
5,5,5,5,5,5,5,5,20,20,20
5,5,5,5,5,5,10,10,10,20,20
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,20
5,5,5,5,10,10,20,20,20
10,10,20,20,20,20
5,5,5,5,10,10,10,10,20,20
5,5,5,5,5,5,5,5,10,10,10,10,20
5,5,10,20,20,20,20
5,5,10,10,10,10,10,10,10,20
5,5,5,5,5,5,10,10,10,10,10,20
5,5,5,5,5,5,10,10,10,10,10,10,10
5,5,5,5,5,5,5,5,5,5,5,5,5,5,10,20
5,5,10,10,10,20,20,20
5,5,5,5,5,5,5,5,5,5,10,10,10,20
10,10,10,10,10,10,10,10,20
5,5,5,5,10,10,10,10,10,10,20
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,10,10
5,5,5,5,5,5,5,5,5,5,5,5,10,10,10,10
5,5,5,5,5,5,5,5,5,5,5,5,20,20
5,5,5,5,5,5,5,5,5,5,5,5,10,10,20
5,5,10,10,10,10,10,10,10,10,10
5,5,5,5,5,5,5,5,5,5,5,5,5,5,10,10,10
5,5,5,5,10,10,10,10,10,10,10,10
5,5,10,10,10,10,10,20,20
10,10,10,10,10,10,10,10,10,10下面是我的程序计算下列数据的结果：因为100太大了，计算比较慢，把N搞小点，大家也可以手动的分析一下结果的正确性。
int[] arr = new int[] {2,3,4,7,8}; N=10 ；
生成的结果如下：共7组
2,4,4,
2,2,2,4,
3,3,4,
2,2,3,3,
3,7,
2,2,2,2,2,
2,8,程序正在整理中，因为N太大时，速度比较慢，过2天再贴出来。

这个题目其实很简单的class count{
static int[][] arr;
static int[] arr0;
public static void main(String[] args){
   arr = new int[][]{{},{},{},{}};
   for(int i = 0 ;i<arr.length;i++)
   {
    for(int j = 0 ;j<arr[i].length;j++){
      arr0[i]=a[i][j];
     }
   }
    for(int k = 0 ;j<arr0.length;k++){if(arr0[k]==100){   System.out.println(arr0[k]);
   }   }

}}
自己没有测试
不知道对不对~~
可能要定义一个集合重新存储以下

调试易

满足条件的排列组合

解决方案 »