c++recursionsubset

What is the use of creating a copy of the input in a recursive call?


This is a code to generate all the substrings in of a given vector

class Solution {
public:
    void sub(vector<int> &ip, vector<int> &op, vector<vector<int>> &ans) {
    if (ip.size() == 0) {
        ans.push_back(op);
        return;
    }

    // Create a copy of ip to avoid modifying the original vector
    vector<int> ip_copy(ip);

    vector<int> op_one = op;
    vector<int> op_two = op;
    op_two.push_back(ip_copy[0]);
    ip_copy.erase(ip_copy.begin());

    sub(ip_copy, op_one, ans);
    sub(ip_copy, op_two, ans);
    return;
}

vector<vector<int>> subsets(vector<int> &nums) {
    vector<vector<int>> ans;
    vector<int> op;
    sub(nums, op, ans);
    return ans;
}

};

my questions is, why must I create a copy of the ip? When the copy is passed into the next recursive call, why can't I use the original input only? (apart from ofcourse, preserving info)

This code below, does not give the substring that have more than one integer in them..

class Solution {
public:
void sub(vector<int> &ip, vector<int> &op, vector<vector<int>> &ans) {
    if(ip.size() == 0) {
        ans.push_back(op);
        return;
    }
    vector<int> op_one = op;
    vector<int> op_two = op;
    op_two.push_back(ip[0]);
    ip.erase(ip.begin());
    sub(ip, op_one, ans);
    sub(ip, op_two, ans);
    return;
}
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> op;
    sub(nums, op, ans);
    return ans;
}

};


Solution

  • When the copy is passed into the next recursive call, why can't I use the original input only?

    Because the original ip is a reference. If you don't copy it, the first recursive call modifies it before the second call.

    If you do copy it then each sibling call has the same state.

    However I find it very suspicious to have a function that accepts by reference and copies in the body. Much simpler is to just take by value.

    class Solution {
    public:
    vector<vector<int>> subsets(vector<int> ip, vector<int> op = {}) {
        if(ip.size() == 0) {
            return { op };
        }
        int value = ip[0];
        ip.erase(ip.begin());
        vector<vector<int>> ans_one = sub(ip, op);
        op.push_back(value);
        vector<vector<int>> ans_two = sub(ip, op);
        ans_one.insert(ans_one.end(), ans_two.begin(), ans_two.end());
        return ans_one;
    }