[C++] Explained heuristic DFS 296ms faster than 77%
Firstly, sum up all positive number as base, sort numbers as abs value and try to search a combination of numbers to subtract from base.\nObserver that 2^11 = 2
Firstly, sum up all positive number as **base**, sort numbers as abs value and try to search a combination of numbers to subtract from **base**.\nObserver that 2^11 = 2048 >= 2000 so we will never pick more than 11 elements\n\nThen, loop through how many numbers we will pick, use a stack to maintain the combinations. Whenever the stack size is greater than k, pop until the size becomes k.\n\nA very important pruning:\nIf we have **x** numbers left to pick, and number in currenct index is **v**, when stack already has k elements, then **x * v < pq.top()** must be satisified, otherwise it\'s not possible to get a better solution in this branch.\n\n```\nclass Solution {\npublic:\n    priority_queue<long long> candidates;\n    int _k;\n    \n    void dfs(vector<int> &a, int index, int pick, long long val) {\n        if (pick == 0) {\n            candidates.push(val);\n            while (candidates.size() > _k) candidates.pop();\n            return;\n        }\n        if (index >= a.size()) return;\n        // Important prune!!\n        if (candidates.size() == _k && (long long) pick * a[index] + val >= candidates.top()) return;\n        \n        dfs(a, index + 1, pick - 1, val + a[index]);\n        dfs(a, index + 1, pick, val);\n    }\n    \n    long long kSum(vector<int>& a, int k) {\n        long long base = 0;\n        _k = k;\n        for (int i = 0; i < a.size(); i ++) {\n            if (a[i] > 0) base += a[i];\n            else a[i] = -a[i];\n        }\n        sort(a.begin(), a.end());\n        \n        candidates.push(0);\n        // Only select one\n        for (int i = 0; i < k && i < a.size(); i ++) candidates.push(a[i]);\n        \n        for (int pick = 2; pick <= 10; pick ++) {\n            dfs(a, 0, pick, 0LL);\n        }\n        \n        return base - candidates.top();\n    }\n};\n```\n\nAn even greedier pruning strategy is to use the interval sum instead of **x * v**.
[]