回溯：77、组合
在本题中，c++很好理解，但是在书写java的时候有一个需要注意的知识盲区：
//Java class Solution { public List path = new linkedList<>(); public List > res = new linkedList<>(); public List> combine(int n, int k) { traversal(n, k, 1); return res; } public void traversal(int n, int k, int startIndex){ if(path.size() == k){ res.add(new linkedList<>(path));/ return; } for(int i = startIndex; i <= n; i++){ path.add(i); traversal(n, k , i + 1); path.remove(path.size() - 1); } } }
res.add(new linkedList<>(path));
将当前path保存在res中的时候需要调用List类中的复制方法，否则res中仅仅保存了多个path的引用，导致最后res输出了六个空List（[[],[],[],[],[],[]]）。这是和c++不一样的。
//附c++ class Solution { public: vector path; vector > res; vector> combine(int n, int k) { path.clear(); res.clear(); traversal(path, res, n, k, 1); return res; } void traversal(vector &path, vector > &res, int n, int k, intstartindex){ if(path.size() == k){ res.push_back(path); return; } for(int i = startindex; i <= n; i++){ path.push_back(i); traversal(path, res, n, k, i + 1); path.pop_back(); } } };