CODEWITHSUNDEEP
javaarrays
user3691951
user3691951

Reputation: 45

Java Calculate all possible combinations of given int array

I am trying to construct a program that would take an array of int({1,2,3} and a length value and calculate all possible combinations of this array.

For example:

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

This will output:

 00
 10
 01
 11

But i keep getting a Stack overflow error when i try to call the possiblecomb in the for loop

 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();
        }
    }
}

}

Upvotes: 2

Views: 4448

Answers (2)

Andr&#233; Luiz Ferreira Pinto
Andr&#233; Luiz Ferreira Pinto

Reputation: 475

As @MichaelCMS said you never stop the recursion, hence a stack overflow.

If you don't mind using Lists instead of arrays this is a solution:

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);
  }
}

That gives you:

00
01
10
11

Upvotes: 3

MichaelCMS
MichaelCMS

Reputation: 4763

Try moving your recursive call outside of the for.

You are using the for in order to copy contents.

Your end variable will eventually increment above max lenght, and your (==) comparison won't be a stopper.

Take the example where num.Length = 2 and end is 2 :

You will call your function once with end = 3 which will stop and print inside the recursive call, and next, when i == 1 your end will be 4 and the recursive call won't break.

If you want to avoid the infinite recurssion with your current code in order to better debug with output, put the break condition

if (end>=maxLength)

Upvotes: 3

Related Questions