Why does similar code has different runtime and memory usage?

Question

I solved this problem on leetcode using recursion. I dabbled with different versions of my solution and I found that runtime and memory usage vary along several parameters.When I switched from for-loop to while loop runtime decreased from 92ms to 56ms. I also had used a redundant else, which when removed gave further decrease in runtime from 56 to 40ms, memory usage remaining the same. I saw other solution which was significantly faster than mine and was using only one third of memory. My final version is almost similar to the one I saw, but still is twice as slow. My solution:

    class Solution {
public:
      static void solver(vector<int>candidates, int target, vector<int> path, int index, vector<vector<int>>&res){
          if(target == 0){
              if(find(res.begin(), res.end(), path) == res.end())
              res.push_back(path);
              return;
          }
          else if(target < 0){
              return;
          }
  
          else{

            //   both of these work!!! but for loop(92ms) is slower than while loop(56ms) memory usage being 28MB.
            // If I remove else further runtime would improve to 40ms

            //   for(int i = index; i< candidates.size() && target-candidates[i] >= 0; i++){
            //       path.push_back(candidates[i]);
            //       solver(candidates, target-candidates[i], path, i+1, res);
            //       path.pop_back();
            //   }

            while(index < candidates.size() && target-candidates[index] >= 0){
                path.push_back(candidates[index]);
                solver(candidates, target-candidates[index], path, index+1, res);
                index++;
                path.pop_back();
            }
          }
      }

      static vector<vector<int>> combinationSum2(vector<int>&candidates, int target){
          vector<vector<int>> res;
          vector<int> path;
          int index{0};
          sort(candidates.begin(), candidates.end());
          solver(candidates, target, path, index, res);
          return res;
      }


};

The Solution I found: It is faster than any hack above, it took 20ms and 10.8MB of space. What could be the reason even though my final version is almost similar to this one.

 vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
         vector<vector<int>> sol;
         vector<int> v;
        sort(candidates.begin(),candidates.end());
         int i=0;
         permute(candidates,target,i,v,sol);
        return sol;
    }
    void permute(vector<int>& candidates,int target,int i,vector<int> &v,vector<vector<int>> &sol)
    {
        if(target==0)
        {
            if(find(sol.begin(),sol.end(),v)==sol.end())
                sol.push_back(v);
            return;
        }
        if(target<0)
            return;
        while(i<candidates.size() && target-candidates[i]>=0)
        {
            v.push_back(candidates[i]);
             permute(candidates,target-candidates[i],i+1,v,sol);
            i++;
             v.pop_back();
        }
    }

In for loop there would be an extra copy of variable i, that can be understood among other thing.

Answer 1

The key difference is most likely that permute takes the candidates and path vector by reference.

void permute(vector<int>& candidates,int target,int i,vector<int> &v,vector<vector<int>> &sol)

solver on the other hand copies the vectors.

static void solver(vector<int>candidates, int target, vector<int> path, int index, vector<vector<int>>&res)

Since the function is repeatedly called in the recursion, this can add up to significant memory and time.

Answer 2

Because LeetCode's benchmarking measurements are not accurate, you can just ignore those data.

This'll also pass through:

#include <cstdint>
#include <vector>
#include <algorithm>

struct Solution {
    std::vector<std::vector<int>> combinationSum(
                                   std::vector<int>& candidates,
                                   const int target
    ) {
        std::sort(std::begin(candidates), std::end(candidates));
        std::vector<std::vector<int>> combinations;
        std::vector<int> combination;
        depthFirstSearch(candidates, target, combinations, combination, 0);
        return combinations;
    }

private:
    void depthFirstSearch(
        std::vector<int>& candidates,
        int target,
        std::vector<std::vector<int>>& combinations,
        std::vector<int>& combination,
        std::size_t start
    ) {
        if (!target) {
            combinations.push_back(combination);
            return;
        }

        for (std::size_t i = start; i != std::size(candidates) && target >= candidates[i]; ++i) {
            combination.push_back(candidates[i]);
            depthFirstSearch(candidates, target - candidates[i], combinations, combination, i);
            combination.pop_back();
        }
    }
};

---

References

• For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2} in there.