通过回溯算法设置Java功能

Question

我似乎有一个关于使用回溯实现功率集算法的问题。我想要实现的是相当简单的，生成任何给定数字的功率集： Ex。 [1 2 3] => [1] [2] [3]; [1,2] [1,3] [2,3]; [1,2,3]

我的算法使用堆栈来放置数字，它将数字添加到堆栈并发送它们进行计算。代码如下：

public int calculatePowerSet(int x, LinkedList<Integer> arr) 
{ 
    int size = 1; 
    int nrOfTimes=0; 
    int calculate =0; 
    boolean goOn=true; 
    Stack<Integer> stack = new Stack<Integer>(); 
    int k=0, len = arr.size(); 
    double temp=0.0f; 
    while(size<=len) 
    { 
     goOn=true; 
     stack.push(arr.get(0)); 
     k = arr.indexOf(stack.peek()); 
     temp = size; //ignore these as they are for calculating time 
     temp/=len;  //ignore these as they are for calculating time 
     temp*=100;  //ignore these as they are for calculating time 
     setPowerSetPrecentage((int)temp); 
     while(goOn) 
     { 
      if(isStopProcess())return 0; 
      if((k==len)&&(stack.size()==0)) goOn=false; 
      else if(stack.size()==size) 
      { 
       String sign = ""; 
       if((stack.size()%2)==0) sign="+"; 
       else sign="-"; 
       calculate =calculateSets(stack.toArray(), sign, calculate, x); 
       k = arr.indexOf(stack.pop())+1; 
      } 
      else if(k==len) 
       k = arr.indexOf(stack.pop())+1; 
      else 
      { 
       prepereStack(stack,arr.get(k)); 
       k++; 
      } 
     } 
     size++; 
    } 
    return calculate; 
} 

这里是计算方法：

private int calculate(int[] arr2, int x) 
{ 
     int calc=1; 

     float rez = 0; 
     for(int i=0;i<arr2.length;i++) 
      calc*=arr2[i]; 
     rez = (float)(x/calc); 
     calc = (int) (rez+0.5d); 
     return calc; 
} 

代码似乎所有数字娄20被完美的工作，但在那之后我似乎得到错误的结果。我无法通过数字手动检查，因为有数百种组合。例如，对于25个数字的一​​个输入，我应该得到1229的结果，而不是我得到1249.我不确定我错过了什么，因为我认为该算法应该在理论上工作，所以如果有人有任何建议，将是伟大的。

Answer 1

我会建议从你的计算中分离出发电机组的代。虽然有一些非常有效的发电机组算法，但我建议保持它非常简单，直到您需要提高效率。

private void forEachSet(List<Integer> currentSet, List<Integer> rest) { 
    if (rest.isEmpty()) { 
     process(currentSet); 
    } else { 
     Integer nextInt = rest.remove(0); 
     forEachSet(currentSet, rest); 
     currentSet.add(nextInt); 
     forEachSet(currentSet, rest); 
     current.remove(nextInt); 
     rest.add(nextInt); 
    } 
} 

public forEachSet(List<Integer> set) { 
    forEachSet(new ArrayList<>(), new ArrayList<>(set)); 
}