javarecursionmathcombinatoricsrecursive-backtracking

Create a list of combinations recursively


I am trying to implement a combination method using recursion. I have already done it using a for loop but want to approach it via recursion.

The method gets two inputs and creates all possible combinations. It is supposed to store the combination in an instance variable that I have called "combination". I tried different codes but they don't work properly. I think recursive back-tracking is the best way to approach this.

For example, object.pe1.combination(4,3) would create something like this: image of combination list


    // Instance variable needed for this problem
    ArrayList<Integer[]> combination; 
    private int size;



    // To calculate all the possible combinations
    private int factorial(int x){
        if (x == 0) {
            return 1;
        }
        else {
            return x * factorial(x - 1);
        }
    }
    
    void combination(int n, int r) {
        
        // formula for calculating the combination of r items selected among n: n! / (r! * (n - r)!)
        int noc = factorial (n) / (factorial (r) * factorial (n - r)); // number of combinations 
        
        this.combination = new ArrayList<Integer[]>(noc); // 2D array. Each slot stores a combination

        if (noc == 0) {
            
        }
        else {
            this.combination = new ArrayList<Integer[]>(noc);
            int[] arr = new int[n];
            int[] temparr = new int[r];
            arr = createCombination(temparr, 0, r);
        }
    }


        private int[] createCombination(int[] temparr, int index, int r) {
        // this is where I am stuck
        temparr[0] = index;
        
        if (temparr[r] == 0) {
            temparr = new int[r - 1];
            temparr = createCombination(temparr, index + 1, r - 1);
        }
        
        else {
            return temparr;
        }
    }


Solution

  • A recursive implementation of any algorithm is comprised of two parts:

    For this task a base case will be a situation when size of the combination equals to a target size (denoted as r in your code, in the code below I gave it a name targetSize).

    Explanation of the recursive logic:

    The type ArrayList<Integer[]> which you are using to store the combination isn't a good choice. Arrays and generics do not play well together. List<List<Integer>> will be more appropriate for this purpose.

    Also in my code List is used as a source of data instead of an array, which isn't a complicated conversion and can be achieved easily.

    Pay attention to the comments in the code.

        private List<List<Integer>> createCombination(List<Integer> source, List<Integer> comb, int targetSize) {
            if (comb.size() == targetSize) { // base condition of the recursion
                List<List<Integer>> result = new ArrayList<>();
                result.add(comb);
                return result;
            }
    
            List<List<Integer>> result = new ArrayList<>();
            Iterator<Integer> iterator = source.iterator();
            while (iterator.hasNext()) {
                // taking an element from a source
                Integer item = iterator.next();
                iterator.remove(); // in order not to get repeated the element has to be removed
    
                // creating a new combination using existing as a base
                List<Integer> newComb = new ArrayList<>(comb);
                newComb.add(item); // adding the element that was removed from the source
                result.addAll(createCombination(new ArrayList<>(source), newComb, targetSize)); // adding all the combinations generated
            }
            return result;
        }
    

    For the input

        createCombination(new ArrayList<>(List.of(1, 2, 3)), new ArrayList<>(), 2));
    

    It'll produce the output

    [[1, 2], [1, 3], [2, 3]]