k Sum II

Given n unique integers, number k (1<=k<=n) and target.

Find all possible k integers where their sum is target.

http://www.lintcode.com/en/problem/k-sum-ii/

Solution

求所有路径，DP不行了，DFS。Combination Sum问题的变形。超过一分钟写出来都要不好意思了。

class Solution {
public:
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return a list of lists of integer 
     */
    vector<vector<int> > kSumII(vector<int> A, int k, int target) {
        vector<vector<int> > result;
        vector<int> path;
        if(A.size() < k) return result;
        sort(A.begin(), A.end());
        dfs(A, k, target, path, result, 0);
        return result;
    }
    void dfs(vector<int> &A, int k, int gap, vector<int> &path, vector<vector<int> > &records, int pos) {
        if(path.size() == k) {
            if(gap == 0) {
                records.emplace_back(path);
            }
            return;
        }
        for(int i=pos; i< A.size(); i++) {
            if(A[i] > gap) {
                break;
            }
            path.emplace_back(A[i]);
            dfs(A, k, gap-A[i], path, records, i+1);
            path.pop_back();
        }
    }
};