void KSum(vector<int> &num, vector<int> &ans, int start, int k, int target) { int len = (int)num.size(); if (k == 2) { int L = start, R = len-1; unordered_set<int> hasher; while (L < R) { if (target == num[L] + num[R]) { ans[K-2] = num[L]; ans[K-1] = num[R]; if (hasher.find(num[L]) == hasher.end()) { result.push_back(ans); hasher.insert(num[L]); } L++; R--; } else if (target < num[L] + num[R]) R--; else L++; } } else { for (int i = start; i < len-2; i++) { if (i>start && num[i]==num[i-1]) continue; ans[K-k] = num[i]; KSum(num, ans, i+1, k-1, target-num[i]); } } }
递归过程
分解子问题一直到2Sum,这个用两个指针就可以解决了
【最近手残好难过,正确率好低】