Instantiation of List (Java)

动机

今天刷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的解