Combination Sum II -- LeetCode

 

這道題跟Combination Sum非常相似，不了解的朋友可以先看看，唯一的區別就是這個題目中單個元素用過就不可以重復使用了。乍一看好像區別比較大，但是其實實現上只需要一點點改動就可以完成了，就是遞歸的時候傳進去的index應該是當前元素的下一個。代碼如下：

 

public ArrayList> combinationSum2(int[] num, int target) {
    ArrayList> res = new ArrayList>();
    if(num == null || num.length==0)
        return res;
    Arrays.sort(num);
    helper(num,0,target,new ArrayList(),res);
    return res;
}
private void helper(int[] num, int start, int target, ArrayList item,
ArrayList> res)
{
    if(target == 0)
    {
        res.add(new ArrayList(item));
        return;
    }
    if(target<0 || start>=num.length)
        return;
    for(int i=start;istart && num[i]==num[i-1]) continue;
        item.add(num[i]);
        helper(num,i+1,target-num[i],item,res);
        item.remove(item.size()-1);
    }
}

在這裡我們還是需要在每一次for循環前做一次判斷，因為雖然一個元素不可以重復使用，但是如果這個元素重復出現是允許的，但是為了避免出現重復的結果集，我們只對於第一次得到這個數進行遞歸，接下來就跳過這個元素了，因為接下來的情況會在上一層的遞歸函數被考慮到，這樣就可以避免重復元素的出現。這個問題可能會覺得比較繞，大家仔細想想就明白了哈。