题解 | 递归回溯 #组合# [P1]

就是递归去暴力枚举. 

后选的数必须比之前选的大(之前选的数用last记录, last初始为0), 
以保证不会有重复(i.e. 不会出现同时输出[1,2]和[2,1])。

用回溯去避免不必要的array copy.
i.e 回溯是basecase输出的时候才copy
    不回溯是每一次recurse都要copy, 输出时不用copy.

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
  
    public ArrayList<ArrayList<Integer>> combine (int n, int k) {
      recurse(0 /* last */, n, k, new ArrayList<>());
      return ans;
    }
  
    void recurse(int last, int n, int k, ArrayList<Integer> partial) {
      if (partial.size() == k)
        ans.add(new ArrayList<>(partial));  // add a copy to ans
      
      for (int i = last+1; i <= n; i++) {
        partial.add(i);
        recurse(i, n, k, partial);
        partial.remove(partial.size()-1);  // 回溯
      }
    }
}