Combinations -- LeetCode

 
這道題是NP問題的題目，時間復雜度沒辦法提高，用到的還是N-Queens中的方法：用一個循環遞歸處理子問題。實現的代碼跟Combination Sum非常類似而且更加簡練，因為不用考慮重復元素的情況，而且元素只要到了k個就可以返回一個結果。代碼如下：

public ArrayList> combine(int n, int k) {
    ArrayList> res = new ArrayList>();
    if(n<=0 || n(), res);
    return res;
}
private void helper(int n, int k, int start, ArrayList item, ArrayList> res)
{
    if(item.size()==k)
    {
        res.add(new ArrayList(item));
        return;
    }
    for(int i=start;i<=n;i++)
    {
        item.add(i);
        helper(n,k,i+1,item,res);
        item.remove(item.size()-1);
    }
}