public class Combinations {

    public static void main(String[] args) {
        int n = 4;
        int k = 2;

        List<List<Integer>> ans = combine(n, k);

        System.out.println(ans);
    }

    public static List<List<Integer>> combine(int n, int k) {
        List<Integer> track = new ArrayList<>();

        List<List<Integer>> ans = new ArrayList<>();

        recurse(1, n, k, track, ans);

        return ans;
    }

    private static void recurse(int depth, int n, int k, List<Integer> track, List<List<Integer>> ans) {
        if (track.size() == k) {

            // create a new copy, do not refer to it
            List<Integer> sol = new ArrayList<>(track);

            ans.add(sol);

            return;
        }

        // Below code should not be place at the head of function, if not, mistakes occurs
        if (depth > n) {
            return;
        }

        track.add(depth);
        recurse(depth + 1, n, k, track, ans);
        track.remove(track.size() - 1);

        recurse(depth + 1, n, k, track, ans);
    }
}