2015-11-23 100 views
2

我一直在試圖理解,使用深度優先搜索(DFS)下面的代碼打印出長度爲k的包括數字的所有獨特的組合[1..1]Java的ArrayList的初始化

請參閱該行私人DFS功能

public ArrayList<ArrayList<Integer>> combine(int n, int k) { 
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); 
    if (n <= 0 || n < k) 
     return result; 
    ArrayList<Integer> item = new ArrayList<Integer>(); 
    dfs(n, k, 1, item, result); 
    return result; 
} 

private void dfs(int n, int k, int start, ArrayList<Integer> item, 
     ArrayList<ArrayList<Integer>> res) { 
    if (item.size() == k) { 
     res.add(new ArrayList<Integer>(item)); /*doubt*/ 
     return; 
    } 

    for (int i = start; i <= n; i++) { 
     item.add(i); 
     dfs(n, k, i + 1, item, res); 
     item.remove(item.size() - 1); 
    } 
} 

評論說:「疑問」如果我把它改爲res.add(項目)返回結果爲空列表的列表。 ListObject.add(E e)是一個完全有效的函數,爲什麼它不起作用?

+2

因爲您正在修改for循環中'item'指向的同一列表。這也將修改存儲在'res'列表中的參考列表。 –

回答

1

所以你的問題涉及到這兩個備選方案:

// works 
res.add(new ArrayList<Integer>(item)); 

// won't work, results in empty lists 
res.add(item); 

new ArrayList<Integer>(item)的目的是創建一個新的列表具有相同內容的原始,有效地克隆原。

如果您不克隆原始文件,它將保持空白。第一次dfs叫,item是空的,然後看這個循環:

for (int i = start; i <= n; i++) { 
    item.add(i); 
    dfs(n, k, i + 1, item, res); 
    item.remove(item.size() - 1); 
} 

的每一個元素添加到item稍後將刪除。這就是爲什麼你最終得到沒有克隆步驟的空列表。如果不克隆,不僅會得到一個空列表清單,而且所有空列表實際上都與combine中創建的ArrayList相同,在第一次撥打dfs之前。

1

這是因爲item.remove(item.size() - 1);正在修改剛剛添加到結果列表中的相同列表。所以它總是最終刪除所有的項目。您擁有的解決方案實際上是複製項目列表並將它們存儲在結果列表中。沒有人對該列表有任何參考,因此不會被修改。