Hackerrank N-Sum

Hackerrank_NSum.cpp

vector<vector<int>> ans;   // Stores the final answer.
    
/* Skip the duplicates. */
int increment(vector<int>& nums, int cur) {
    int n = nums.size();
    int j=cur+1;
    while (j < n && nums[j] == nums[cur]) {
        j++;
    }
    return j;
}

/* Skip the duplicates. */
int decrement(vector<int>& nums, int cur) {
    int j=cur-1;
    while (j >= 0 && nums[j] == nums[cur]) {
        j--;
    }
    return j;
}

/* Pairs of numbers in array `nums` from index `start` to
 * index `end` with sum `target`.
 */
void twoSum(vector<int>& nums, int start, 
            int end, int target, vector<int> a) {
    while (start < end) {
        if (nums[start]+nums[end] == target) {
            vector<int> temp = a;
            temp.push_back(nums[start]);
            temp.push_back(nums[end]);
            ans.push_back(temp); 
            start = increment(nums, start);
            end = decrement(nums, end);
        } else if (nums[start]+nums[end] < target) {
            start = increment(nums, start);
        } else {
            end = decrement(nums, end);
        }
    }
}

// O(n^(k-1))
void nSum(vector<int> &arr, int k, int start, int end, int target, vector<int> chosen) { // T(k) = n*T(k-1) + O(1)
    if (k < 2) {  // 1
        return ;
    }
    if (k == 2) {   // 1
        twoSum(arr, start, end, target, chosen); // O(n)
        return;
    }
    for (int i=start; i<=end; i=increment(arr, i)) { // n*
        int fixed = arr[i];  //  1
        chosen.push_back(fixed); // 1
        nSum(arr, k-1, i+1, end, target-fixed, chosen); // T(k-1)
        chosen.pop_back(); // 1
    }
}

int findNSum(vector<int> arr, int k, int target) { // O(n^(k-1))
    sort(arr.begin(), arr.end());    // O(nlogn)
    int start = 0;           // 1
    int end = arr.size()-1;  // 1
    vector<int> chosen;     // 1
    nSum(arr, k, start, end, target, chosen); // O(n^(k-1))
    return ans.size(); // 1
}