Combination Sum -- LeetCode

 

這個題是一個NP問題，方法仍然是N-Queens中介紹的套路。基本思路是先排好序，然後每次遞歸中把剩下的元素一一加到結果集合中，並且把目標減去加入的元素，然後把剩下元素（包括當前加入的元素）放到下一層遞歸中解決子問題。算法復雜度因為是NP問題，所以自然是指數量級的。代碼如下：

 

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

注意在實現中for循環中第一步有一個判斷，那個是為了去除重復元素產生重復結果的影響，因為在這裡每個數可以重復使用，所以重復的元素也就沒有作用了，所以應該跳過那層遞歸。這道題有一個非常類似的題目Combination Sum II，有興趣的朋友可以看看，一次搞定兩個題哈。