Combinations | Leetcode

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

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

---

Solution: First initialize the answer list before calling the recursive function. In the recursive function, put the termination condition first. When we have the list size == k, then we know this result is ripe for reaping. Save this result and then return. Otherwise, loop from the given starting index of this recursive call. In each loop, add the first character at the given starting index, call itself recursively, and then remove the added character. Doing so will let you collect all the C(n,k) combinations. But unfortunately it is a bit hard to explain why!

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> answer = new ArrayList<>();
        combine(answer, new ArrayList<Integer>(k), 1, n, k);
        return answer;
    }
    
    public void combine(List<List<Integer>> answer, List<Integer> list, int start, int n, int k) {
        if (list.size() == k) {
            answer.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = start; i <= n; i++) {
            list.add(i);
            combine(answer, list, i + 1, n, k);
            list.remove(list.size() - 1);
        }
    }
}