排列组合

Question

如题，求这算法是以前论坛里出现过的，看到了，小弟搞了好长时间。
/**任意给一数组,如{-10,45,35,99,10,6,9,20,17,18}
 * 再任意给一个值,如35.
 * 请从上面的数组中找出所有的组合,使他们的和等于任意一个值，如：35.
 * 注意,每一种组合中一个数只能出现一次。
 * @param args
 * @throws Exception 
 */
想给答案：
35
-10,45
17,18
-10,35,10
6,9,20
-10,10,17,18
-10,10,6,9,20我机子里运行出来的，不知道哪位有更好的算法，有人说背包算法，在下道行过浅。灌水的兄弟就算了。。
不要、接分、sf什么的
如果有人有好算法，贴出来。大家共享学习下

Answer 1

public static void main(String[] args) throws Exception, IOException {
int[] arr = {1,2,3,4,5};
BufferedReader strin=new BufferedReader(new InputStreamReader(System.in));
int a = Integer.parseInt(strin.readLine());

print(arr,a);

}

public static void print(int[] arr,int a){
int count = 0;
for(int i=0;i<arr.length;i++){
if(arr[i]==a){
System.out.println(i);
}else{
count++;
}
}
if(count==arr.length){
System.out.println("-1");
}
}

Answer 2

class Hao {
ArrayList<String> list = new ArrayList<String>(); /**
 * 比较任意一个数==35
 * 
 * @param array
 */
public void Show0(int[] array) {
for (int a : array) {
if (a == 35) {
list.add(a + "");
}
}
} /**
 * 比较任意两个数==35
 * 
 * @param a
 */
public void Show1(int[] a) {
for (int i = 0; i < a.length; i++) {
for (int j = i + 1; j < a.length; j++) {
/* 任意两个数,如果相等则存起来 */
if (a[i] + a[j] == 35) {
list.add(a[i] + "," + a[j]);
}
/* 进行任意三个数==35 的比较 */
Show2(a, i, j);
}
}
} /**
 * 比较任意三个数==35
 * 
 * @param a
 * @param i
 * @param j
 */
public void Show2(int[] a, int i, int j) {
int num = a[i] + a[j];// 任意两个数之和 for (int z = 0; z < a.length; z++) {
/* 在数组中排除,选出的任意两个数 */
if (z == i || z == j)
continue;
/* 任意三个数,如果相等则存起来 */
if (num + a[z] == 35) {
/* 已选的三个数排个序 */
int[] dd = { a[i], a[j], a[z] };
Arrays.sort(dd);
/* 存储 */
list.add(dd[0] + "," + dd[1] + "," + dd[2]);
}
/* 进行任意四个数==35 的比较 */
Show3(a, i, j, z);
}
} /**
 * 比较任意四个数==35
 * 
 * @param a
 * @param i
 * @param j
 * @param z
 */
public void Show3(int[] a, int i, int j, int z) {
int num = a[i] + a[j] + a[z];// 任意三个数之和 for (int k = 0; k < a.length; k++) {
/* 在数组中排除,选出的任意三个数 */
if (k == i || k == j || k == z)
continue;
/* 任意四个数,如果相等则存起来 */
if (num + a[k] == 35) {
/* 已选的四个数排个序 */
int[] dd = { a[i], a[j], a[z], a[k] };
Arrays.sort(dd);
/* 存储 */
list.add(dd[0] + "," + dd[1] + "," + dd[2] + "," + dd[3]);
}
/* 进行任意5 ,6~~~~~ 个数==35 的比较 */
}
}
}public class Test02 {
public static void main(String[] args) {
int[] array = { -10, 45, 35, 99, 10, 6, 9, 20, 17, 18 }; Hao h = new Hao();
h.Show0(array);
h.Show1(array);
/* 输入结果 */
for (String in : h.list) {
System.out.println(in);
}
}}

Answer 3

    写了个非递归的算法，主要利用“广度优先搜索”思想,可以匹配“任意”个数的数字；
但未进行贪心，所以效率不是很高；
希望大家可以找到类似于“优先选择出口最小的进行搜索”这样的“贪心策略”，提高程序运行效率。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;import org.junit.Test;/**
 * 背包类，容积可以为负
 *
 */
class Element{

/**
 * 容积
 */
private int count;

/**
 * 空间树的层数，用于检测是否已经到达叶子
 */
private int ceng;

/**
 * 还剩余的容积
 */
private int cha;

/**
 * 父节点指针
 */
private Element parent;
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public int getCeng() {
return ceng;
}
public void setCeng(int ceng) {
this.ceng = ceng;
}
public int getCha() {
return cha;
}
public void setCha(int cha) {
this.cha = cha;
}
public Element getParent() {
return parent;
}
public void setParent(Element parent) {
this.parent = parent;
}
public Element(int count, int ceng, int cha, Element parent) {
super();
this.count = count;
this.ceng = ceng;
this.cha = cha;
this.parent = parent;
}
public Element(int count, int ceng, int cha) {
super();
this.count = count;
this.ceng = ceng;
this.cha = cha;
}
public Element() {
super();
}
@Override
public String toString() {
return "Element [ceng=" + ceng + ", cha=" + cha + ", count=" + count
+ "]";
}

}
/**
 * 自定义的比较器，用于去掉重复的集合
 * 例如：{1,3,2}和{3,2,1}就是重复的，
 * 我们先把他们排序，然后利用归并的思想依次检测
 *
 */
class MyComp implements Comparator<ArrayList<Integer>>{ @Override
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
int i=0,j=0;
while(i<o1.size()&&j<o2.size()){
if(o1.get(i)!=o2.get(j)){
return o1.get(i)-o2.get(j);
}else{
i++;
j++;
}
}
return 0;
}

}
public class Zuhe { /**
         类似于着色、迷宫、骑士巡游等等回溯问题的非递归解法。
中心思想:
 * 将“先序遍历的深度优先递归树”转换为“层序遍历的广度优先空间树”
 * 
 * 假设大容器的体积是sum，有array.length个小容器
 * 生成array.length个根节点，压入队列
 * 调用doOneRoot函数，分别处理这几个根节点
 */
public void beibao(int sum,int[] array){
totalList=new TreeSet<ArrayList<Integer>>(new MyComp());
for(int i:array){
Queue<Element> que=new LinkedList<Element>();
Element root=new Element(i, 1, sum-i, null);
if(root.getCha()==0){
addToSet(root);
}else{
que.offer(root);
}
this.doOneRoot(sum, array, que);
}
System.out.println("只考虑组合的情况下，一共"+totalList.size()+"种方案");
for(ArrayList<Integer> list:totalList){
System.out.println(list);
}
}

/**
        处理空间树的某个根节点
        当队列不为空时
 *    弹出队头节点,如果已经到达空间树底部，则不生成孩子
 *    否则，对于尚未生成完毕的分支:
 *    1、生成array.length个孩子，并检测新的孩子是否选择了重复容器
 *    2、如果选择了重复容器，说明这个分支不符合目标，"剪掉"
 *    否则，对于符合的情况：
 *       如果剩余容积为0，表示已经到达叶子节点，就添加到结果集；
 *       否则压入队列，继续循环
 *  直到队列为空，退出。
 */
public void doOneRoot(int sum,int[] array,Queue<Element> que){
while(!que.isEmpty()){
Element parent=que.poll();
for(int i:array){
if(parent.getCeng()<array.length){
Element child=new Element(i, parent.getCeng()+1, parent.getCha()-i,parent);
boolean flag=this.checkValid(child);
if(flag==true){
if(child.getCha()==0){
addToSet(child);
}else{
que.offer(child);
}
}
}

}
}

}
/**
 * 由当前叶子节点向上回溯，看看是否选择了重复的容积;这个检测方法和"八皇后"极为类似
 */
public boolean checkValid(Element p){
int count=p.getCount();
p=p.getParent();
while(p!=null){
if(p.getCount()==count){
return false;
}
p=p.getParent();
}
return true;
}

/**
 * 最终的结果集
 */
TreeSet<ArrayList<Integer>> totalList;


/**
 * 把符合条件的结果添加到结果集(会自动调用MyComp的compare方法检测是否重复)
 */
public void addToSet(Element child){
ArrayList<Integer> oneList=new ArrayList<Integer>();
while(child!=null){
oneList.add(child.getCount());
child=child.getParent();
}
Collections.sort(oneList);
totalList.add(oneList);
}

@Test
public void test(){
int sum=35;
int[] array={-10,45,35,99,10,6,9,20,17,18};
this.beibao(sum, array);
}
}结果：
只考虑组合的情况下，一共7种方案
[-10, 6, 9, 10, 20]
[-10, 10, 17, 18]
[-10, 10, 35]
[-10, 45]
[6, 9, 20]
[17, 18]
[35]