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;
}
};
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;
}