K sum problem

2SUM I

vector<int> twoSum(vector<int> &nums, int target) {
// write your code here
map<int,int>m;
vector<int> res;
for(int i=0;i<nums.size();i++){
if(m[nums[i]]){
res.push_back(m[nums[i]]);
res.push_back(i+1);
return res;
}else
m[target-nums[i]]=i+1;
}

}

2 SUM II

vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> res;
int left = 0,right = numbers.size()-1;
while(left<right){
if(numbers[left]+numbers[right]==target){
res = {left+1,right+1};
return res;
}else if(numbers[left]+numbers[right]>target)
right--;
else
left++;
}
return res;
}

2 SUM III

class TwoSum {
public:
   void add(int number) {
   m[number]++;
   }

   bool find(int value) {
   for(auto it=m.begin();it!=m.end();it++){
   if(value - it->first == it->first){
   if(it->second>=2)
   return true;
   }else{
   if(m.find(value-it->first)!=m.end())
   return true;
   }
   }
   return false;
   }
private:
unordered_map<int,int>m;
};

3 SUM

void twoSum(vector<int> &numbers, int target,int left,vector<vector<int> > &res) {
int right = numbers.size()-1;
while(left<right){
if(numbers[left]+numbers[right]==target){
vector<int> tmp = {-target,numbers[left],numbers[right]};
res.push_back(tmp);
left++,right--;
while(numbers[right]==numbers[right+1] && left<right)
right--;
while(numbers[left]==numbers[left-1] && left<right)
left++;

}else if(numbers[left]+numbers[right]>target)
right--;
else
left++;
}
}
vector<vector<int> > threeSum(vector<int> &nums) {
// write your code here
vector<vector<int> > res;
int size = nums.size();
if(size<3)
return res;
sort(nums.begin(),nums.end());
for(int i=0;i<size-2;i++){
if(i>0 && nums[i]==nums[i-1])
continue;
twoSum(nums,-nums[i],i+1,res);
}
return res;
}

3SUM cloest

void twoSum(vector<int> &numbers, int first,int target,int left,int &closest) {
int right = numbers.size()-1;
while(left<right){
int cur = first+numbers[left]+numbers[right];
if(abs(cur-target)<abs(closest-target))
closest = cur;
if(cur ==target){
left++,right--;
while(numbers[right]==numbers[right+1] && left<right)
right--;
while(numbers[left]==numbers[left-1] && left<right)
left++;

}else if(cur>target)
right--;
else
left++;
}
}
int threeSumClosest(vector<int> nums, int target) {
// write your code here
int size = nums.size();
if(size<3)
return 0;
sort(nums.begin(),nums.end());
int closest = nums[0]+nums[1]+nums[2];
for(int i=0;i<size-2;i++){
if(i>0 && nums[i]==nums[i-1])
continue;
twoSum(nums,nums[i],target,i+1,closest);
}
return closest;
}

4SUM

void twoSum(vector<int> &numbers, int first,int second,int left,int target,vector<vector<int> > &res) {
int right = numbers.size()-1;
while(left<right){
if(first+second+numbers[left]+numbers[right]==target){
vector<int> tmp = {first,second,numbers[left],numbers[right]};
res.push_back(tmp);
left++,right--;

while(numbers[right]==numbers[right+1] && left<right)
right--;
while(numbers[left]==numbers[left-1] && left<right)
left++;

}else if(first+second+numbers[left]+numbers[right]>target)
right--;
else
left++;
}
}

vector<vector<int> > threeSum(vector<int> &num,int first,int left,int target,vector<vector<int> > &res) {
int size = num.size();
if(size<3)
return res;
for(int i=left;i<size-2;i++){
if(i>left && num[i]==num[i-1])
continue;
twoSum(num,first,num[i],i+1,target,res);
}
return res;
}

vector<vector<int> > fourSum(vector<int> &nums, int target) {
vector<vector<int> > res;
int size = nums.size();
if(size<4)
return res;
sort(nums.begin(),nums.end());
for(int i=0;i<size-3;i++){
if(i>0 && nums[i]==nums[i-1])
continue;
threeSum(nums,nums[i],i+1,target,res);
}
return res;
}

K SUM I

int kSum(vector<int> A, int k, int target) {
// wirte your code here
int size = A.size();
vector<vector<int>> map(k+1,vector<int>(target+1,0));

for(int i=1;i<=size;i++)
for(int j=min(i,k);j>=1;j--)
for(int t=target;t>=A[i-1];t--){
if(j==1)
map[1][t] += A[i-1]==t?1:0;
else
map[j][t] += map[j-1][t-A[i-1]];
}

return map[k][target];
}

K SUM II

vector<vector<int> > kSumII(vector<int> A, int k, int target) {
// write your code here
vector<vector<int> > res;
vector<int> singleRes;
dfs(res,singleRes,0,A,k,target);
return res;
}
void dfs(vector<vector<int> > &res,vector<int>singleRes, int index,vector<int> &A,int k,int target){
if(k<0 || target<0)
return;
if(k==0 && target==0){
res.push_back(singleRes);
return;
}
for(int i=index;i<=A.size()-k;i++){
singleRes.push_back(A[i]);
dfs(res,singleRes,i+1,A,k-1,target-A[i]);
singleRes.pop_back();
}
}