Combinations method return issue

Question

I have written a method to find all combinations n choose k. When I have it void and simply print out the solutions it works fine. However, I am trying to change it as to return a List<List<Integer>> of all the combinations. I tried returning the solution and returning the recursion call in the if-else respectively but I get an error for unreachable line of code. Below I am trying to carry the list of list through the recursion and return it in the end.

public class Combos {
    public static void main(String[] args) {
        List<Integer> n = new ArrayList<Integer>();
        for (int i = 0; i < 9; i++) {
            n.add(i);
        }
        List<Integer> temp = new ArrayList<Integer>();
        List<List<Integer>> combos = new ArrayList<List<Integer>>();
       // findCombos(n, temp, 3, combos);
        System.out.println(findCombos(n, temp, 3, combos));
    }
    public static List<List<Integer>> findCombos(List<Integer> n, List<Integer> temp, int k, List<List<Integer>> combos) {
        if (k == 0) {
            //System.out.print(temp);
            combos.add(temp);
        }
        else {
            for (int i = 0; i < n.size(); i++) {
                temp.add(n.get(i));
                List<Integer> subList = n.subList(i + 1, n.size());
                findCombos(subList, temp, k - 1, combos);
                temp.remove(temp.size() - 1);
            }
        }
        return combos;
    }
}

The working void method is here:

package client;

import java.util.ArrayList;
import java.util.List;

public class Combos {
    public static void main(String[] args) {
        List<Integer> n = new ArrayList<Integer>();
        for (int i = 0; i < 5; i++) {
            n.add(i);
        }
        List<Integer> temp = new ArrayList<Integer>();
        findCombos(n, temp, 3);
    }
    public static void findCombos(List<Integer> n, List<Integer> temp, int k) {
        if (k == 0) {
           System.out.print(temp);
        }
        else {
            for (int i = 0; i < n.size(); i++) {
                temp.add(n.get(i));
                List<Integer> subList = n.subList(i + 1, n.size());
                findCombos(subList, temp, k - 1);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

Answer 1

This has to do with the temp List and how it's always the same object when it gets added to combos.

Changing this line will correct that:

if (k == 0) {
    combos.add(new ArrayList<Integer>(temp));
}

You have to make a copy because temp is getting mutated. After that, the output is:

[[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 1, 5], [0, 1, 6], [0, 1, 7], [0, 1, 8], [0, 2, 3], [0, 2, 4], [0, 2, 5], [0, 2, 6], [0, 2, 7], [0, 2, 8], [0, 3, 4], [0, 3, 5], [0, 3, 6], [0, 3, 7], [0, 3, 8], [0, 4, 5], [0, 4, 6], [0, 4, 7], [0, 4, 8], [0, 5, 6], [0, 5, 7], [0, 5, 8], [0, 6, 7], [0, 6, 8], [0, 7, 8], [1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 6], [1, 2, 7], [1, 2, 8], [1, 3, 4], [1, 3, 5], [1, 3, 6], [1, 3, 7], [1, 3, 8], [1, 4, 5], [1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 5, 6], [1, 5, 7], [1, 5, 8], [1, 6, 7], [1, 6, 8], [1, 7, 8], [2, 3, 4], [2, 3, 5], [2, 3, 6], [2, 3, 7], [2, 3, 8], [2, 4, 5], [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 5, 6], [2, 5, 7], [2, 5, 8], [2, 6, 7], [2, 6, 8], [2, 7, 8], [3, 4, 5], [3, 4, 6], [3, 4, 7], [3, 4, 8], [3, 5, 6], [3, 5, 7], [3, 5, 8], [3, 6, 7], [3, 6, 8], [3, 7, 8], [4, 5, 6], [4, 5, 7], [4, 5, 8], [4, 6, 7], [4, 6, 8], [4, 7, 8], [5, 6, 7], [5, 6, 8], [5, 7, 8], [6, 7, 8]]

As an example of what is happening, if k is 1, we can follow the logic through for a couple of steps:

// k is 1 so call findCombos with 0
findCombos(subList, temp, k - 1, combos);

// k is 0 so add temp to combos
if (k == 0) {
    combos.add(temp);
}

// on return, immediately mutate temp
temp.remove(temp.size() - 1);