动机
今天刷Leetcode时碰到的一道问题（216. Combination Sum III）：
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
给出的function signature为：
public List<List<Integer>> combinationSum3(int k, int n) {
}
注意此处返回type为List of List
一开始我傻傻中招（Java知识太不扎实），直接用
List<List<Integer>> ls = new List<List<Integer>>();
来创建ls，结果报错：List是interface
这个问题我已多次犯过，每次都不长记性，归根结底是自己基础知识不扎实造成的重复性错误。因此我把本文当作知识点记录，来加深对Java List interface及其引申类的理解。
1. 如何实例化（instantiate）List？
当一个class A implements（实现）了一个interface B，那么A和B就有了is-a的关系，及我们可以用：此处A应为concrete class
B obj = new A();
来实现B的实例化。
注意：A obj = new B()是错误的
那么有哪些classes implement了Java List interface呢？参考Oracle提供的documentation，其中比较常用的有:
ArrayList 和 LinkedList
所以实例化时我们可以用：
List<T> ls1 = new ArrayList<T>();
List<T> ls2 = new LinkedList<T>();
注意，ls只可以调用List所有的函数，而不可以调用ArrayList或LinkedList中的（List interface没有定义）的函数。下面的函数调用会引起compiler error：
ls2.addFirst(e);
如果我们想要调用concrete class A中另外的函数，我们需要类型为A的引用。ArrayList和LinkedList都提供了方便的转换方法：
ArrayList<T> arrayLs = new ArrayList<T>(ls1);
LinkedList<T> linkedLs = new LinkedList<T>(ls2);
若我们想要完成ls2.addFirst(e)，我们可以使用：
linkedLs.addFirst(e);
ls2 = linkedLs;
来达到同样的效果。
2. 如何实例化List of List
在完成了以上的搜索后，再来看如何实例化List<List<Integer>>，这里我犯了第二个错误：
List<List<Integer>> ls = new ArrayList<ArrayList<Integer>>();
这是错误的，引起compiler error：cannot convert ArrayList<ArrayList<Integer>> to List<List<Integer>>
为什么不能用B<B> obj = new A<A>()呢？这里和generic type有关，此处有比较详细的解释。总体来说，A<A>和B<B>不是is-a的关系。
如下才是正确的方法：
List<List<Integer>> ls = new ArrayList<List<Integer>>();
在这里，List<Integer>可以出现在右侧，因为它是以数据类型的形式出现，而不是以Constructor的形式出现。
当我们需要进一步在ls中添加List时，只需要根据1中的例子，来实例化List<Integer>即可
3. 实现List的类之间的比较（ArrayList, LinkedList, Stack, Vector）
//TODO
最后分享一下本题我的答案：
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> rtLs = new LinkedList<>();
if(k <=0 || (n / k) < lvl) return rtLs;
if(k == 1 && n >= lvl && n <= 9) {
LinkedList<Integer> ls = new LinkedList<Integer>();
ls.add(n);
rtLs.add(ls);
return rtLs;
}
for(int i = lvl; i < 10; i++) {
if(i > n) break;
lvl = i+1;
List<List<Integer>> shorterLs = combinationSum3(k-1, n-i);
for(List<Integer> ls : shorterLs) {
LinkedList<Integer> als = new LinkedList<Integer>(ls);
als.addFirst(i);
rtLs.add(als);
}
}
lvl = 1;
return rtLs;
}
private static int lvl = 1;
}
本题容易产生歧义的地方是a unique set of numbers，其中unique比较容易理解，即不可有顺序不同数字相同的重复解，而set这个条件比较容易被忽略，应理解为每个解中的数字只可出现一次，如[3,3,3]就不是n=3, k=9的解
