为什么这段递归代码效率低，内存高？

Question

代码所求问题：
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...

下面的两段代码都是回溯递归，为什么效率和内存在存在巨大差别。
内存上我分析原因可能是函数接口太多形参，效率就不明白了，都有判断target是否小于0，小于零则不再搜索，按道理效率应该差不多。
想知道效率和内存上为什么它们差别那么大，如何避免效率低，内存大的问题。

执行用时292ms 88.6MB

// 组合总和.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include <iostream>
#include <vector>

using namespace std;

void combination(vector<int>&  candiates, int target, int index,
    vector<int> solution, vector<vector<int>>& solutionSum) {

    if (index == candiates.size()) {//递归出口
        return;
    }

    if (target < 0) {//退回上一步，并选择下一个数
        return;
    }
    else if (target == 0) {
        for (int i = 0; i < solution.size(); ++i) {
            cout << solution[i] << " ";
        }
        cout << endl;
        solutionSum.push_back(solution);
        return;
    }
    else {
        //下一步
        solution.push_back(candiates[index]);
        combination(candiates, target - candiates[index], index, solution, solutionSum);
        index++;
        solution.pop_back();
        combination(candiates, target, index, solution, solutionSum);//尝试下一个数
    }
}


vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    void combination(vector<int>&  candiates, int target, int index,
        vector<int> solution, vector<vector<int>>& solutionSum);
    vector<vector<int>> solutionsum;
    int i = 0;
    combination(candidates, target, i, {}, solutionsum);

    return solutionsum;
}

int main()
{
    vector<int> candidates = { 2,3,6,7 };
    int target = 7;

    vector<vector<int>> result;
    result = combinationSum(candidates, target);
}

执行用时 16ms. 内存消耗9.7MB

// 组合总和.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include <iostream>
#include <vector>

using namespace std;
class Solution {
public:
    vector<int> solution;
    vector<int> candidates;
    vector<vector<int>> solutionSum;

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        this->candidates = candidates;
        DFS( 0, target );
        return this->solutionSum;
    }

    void DFS(int start, int target) {
        if (target == 0) {
            this->solutionSum.push_back( this->solution );
            return;
        }

        for (int i = start; i < this->candidates.size(); ++i) {
            if ( (target - this->candidates[i])<0 ) {
                continue;
            }
            this->solution.push_back(this->candidates[i]);
            DFS( i, target - this->candidates[i] );
            this->solution.pop_back();
        }
    }
};

int main()
{
    vector<int> candidates = { 2,3,6,7 };
    int target = 7;
    Solution s;
    vector<vector<int>>  res = s.combinationSum(candidates, target);
    
    for (int i = 0; i < res.size(); i++)
    {
        for (int j = 0; j < res[i].size(); ++j) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
}

Answer 1

方法1 的“尝试下一个数”是用递归做的，方法2 用的循环。这就平白多了很多函数调用。

方法1 的 combination 里有一个参数叫 vector<int> solution ，这个参数每调用一次就会拷贝一次。调用次数多了之后，拷贝 vector 的开销是很大的（包括内存与运行时间）。