Java 计算给定 int 数组的所有可能组合

Question

我正在尝试构造一个程序，该程序将获取一个int（｛1，2，3｝）数组和一个长度值，并计算该数组的所有可能组合。

例如:

int[] arr= new char[] {0,1};
int[] tes  = new int[3];
possiblecomb(2, arr,tes,0);

这将输出：

 00
 10
 01
 11

但是当我尝试在 for 循环中调用可能的梳子时，我不断收到堆栈溢出错误

 import java.util.Arrays;

 public class Program {

public static void main(String[] args) {

    // Create an arr to work with
    int[] test = new int[] {0,1};
     int[] tes  = new int[3];
    // Find all possible combinations of this arr in the string size of 3
    possiblecomb(3, test,tes,0);
}

public static void possiblecomb(int maxLength, int[] nums, int[] curr,int end) {

    // If the current array has reached it's maximum length
    if(end == maxLength) {
        System.out.println(Arrays.toString(curr));

    // Else add each number from the numbs to new array and process these new arrays again
    } else {
        for(int i = 0; i < nums.length; i++) {
            int[] oldCurr = curr.clone();
            curr[end]= nums[i];
            possiblecomb(maxLength,nums,curr,end++);
            curr = oldCurr.clone();
        }
    }
}

}

Answer 1

正如@MichaelCMS所说，你永远不会停止递归，因此会出现堆栈溢出。

如果您不介意使用List而不是数组，这是一个解决方案：

import java.util.*;

public class Program {
  private static List<List<Integer>> combinations(List<Integer> list, int maxLength) {
    return combinations(list, maxLength, new ArrayList(), new ArrayList());
  }

  private static List<List<Integer>> combinations(List<Integer> list, int length, List<Integer> current, List<List<Integer>> result) {
    if (length == 0) {
      List<List<Integer>> newResult =  new ArrayList<>(result);
      newResult.add(current);
      return newResult;
    }

    List<List<List<Integer>>> res3 = new ArrayList<>();
    for (Integer i : list) {
      List<Integer> newCurrent = new ArrayList<>(current);
      newCurrent.add(i);
      res3.add(combinations(list, length - 1, newCurrent, result));
    }

    List<List<Integer>> res2 = new ArrayList<>();
    for (List<List<Integer>> lst : res3) {
      res2.addAll(lst);
    }
    return res2;
  }

  public static void printCombinations(List<Integer> list, int maxLength) {
    List<List<Integer>> combs = combinations(list, maxLength);
    for (List<Integer> lst : combs) {
      String line = "";
      for (Integer i : lst) {
        line += i;
      }
      System.out.println(line);
    }
  }

  public static void main(String[] args) {
    List<Integer> l = Arrays.asList(0, 1);
    printCombinations(l, 2);
  }
}

这给了你：

00
01
10
11

Answer 2

尝试将递归调用移到for之外。

您正在使用for复制内容。

您的最终变量最终将增加到最大长度以上，并且您的（==）比较不会阻止。

例如，num.Length=2，end为2：

您将在 end = 3 的情况下调用您的函数一次，这将在递归调用中停止并打印，接下来，当 i == 1 时，您的结束将是 4，递归调用不会中断。

如果要避免当前代码的无限递归，以便更好地调试输出，请将中断条件

if (end>=maxLength)