[C++] Recursion | 4ms, 99.81% faster |  Code explained clearly
Here I used a very clever technique of reducing any n sum problem to a two sum by using recursing and simplification. The most time saving techniques was the sk
Here I used a very clever technique of reducing any n sum problem to a two sum by using recursing and simplification. The most time saving techniques was the skipping of duplicates and unnecessry cases by using if cases. Read the code carefully and please do **upvote** if you like the approach.\n```\n/*\n  READ THE CODE USING MY MARKERS OF 1 to 10. START WITH THE foursum method AND\n  THEN READ nSum method AND FINALLY TO twoSum.\n*/\nclass Solution {\npublic:\n  vector<vector<int>> twoSum(vector<int> &nums, int target, int start) {\n    vector<vector<int>> result;\n    // 7. Now we iterate through the array taking the two pointer approach and\n    // try to find two values in the array to add to the result.\n    int left = start, right = nums.size() - 1;\n    while (left < right) {\n      int curSum = nums[left] + nums[right];\n      // 8. Now we need to move left pointer forward when sum is less than\n      // target and also to avoid duplicates we do not consider the case when\n      // nums[left] == nums[left - 1]. Here we write left > start to not check\n      // nums[left] == nums[left - 1] when left == start.\n      if (curSum < target || (left > start && nums[left] == nums[left - 1])) {\n        left++;\n      } else if (curSum > target || (right < nums.size() - 1 && nums[right] == nums[right + 1])) {\n        // 9. Now we bring right pointer backwards when we have overshot the\n        // target or when duplicates are recorded(nums[right] == nums[right + 1]\n        // is to check for duplicates).\n        right--;\n      } else {\n        // 10. This is executed when curSum == target.\n        result.push_back({nums[left++], nums[right--]});\n      }\n    }\n    return result;\n  }\n\n  vector<vector<int>> nSum(vector<int> &nums, int target, int start, int n) {\n    vector<vector<int>> result;\n    // 2. If the current start value has reached end or start element times n is\n    // greater than target or target is smaller than last element times n. We\n    // cannot get any solution.\n    if (start == nums.size() || nums[start] * n > target ||\n        target > nums.back() * n) {\n      return result;\n    }\n\n    if (n == 2) {\n      // 3. We simply calculate twoSum when we need to.\n      return twoSum(nums, target, start);\n    }\n\n    // 4. When n > 2, we need to reduce the problem into a twosum problem. This\n    // is done by taking a sub problem. Here we consider the ith element and\n    // call the function itself to calculate sum for (n - 1)th sum with a new\n    // target of (target - nums[i]). Also we should start the call for search\n    // with a start index if i + 1 so as to avoid duplicates. We also consider\n    // skipping nums[i] when nums[i - 1] == nums[i] because the array is sorted\n    // and we will avoid duplicates to be detected.\n    for (int i = start; i < nums.size(); i++) {\n      if (i == start || nums[i - 1] != nums[i]) {\n        for (auto &j : nSum(nums, target - nums[i], i + 1, n - 1)) {\n          // 5. Now the j variable is an iterator to the vectors where a target\n          // of (target - nums[i]) has been achieved and we use this iterator to\n          // add to the vector inside the result where nums[i] is present.\n          result.push_back({nums[i]});\n          // 6. Here, since we just added nums[i] to result, we now insert\n          // inside the vector of {nums[i]} the values which came from the n-1\n          // sum call. These results are concatenated to the nums[i].\n          result.back().insert(end(result.back()), begin(j), end(j));\n        }\n      }\n    }\n    return result;\n  }\n\n  vector<vector<int>> fourSum(vector<int> &nums, int target) {\n    // 1. We need a sorted array\n    sort(begin(nums), end(nums));\n    return nSum(nums, target, 0, 4);\n  }\n};\n```
['Recursion', 'C']