So i'm working on solving a combinational problem (find the powerset) using recursive backtracking and noticed that there is a template to do backtracking problems.
problem statement: Given a set of distinct integers, nums, return all possible subsets (the power set).
For a given set of N distinct integers there are 2^N combinations. So one can compute it using the following algorithm where 'cur' stores the partial combination, and 'allSubsets' is called itself 2 times within its body: 1 without the i'th element added to 'cur', and the 2nd call after the i'th element added to 'cur' (after cur.emplace_back and before cur.pop_back)
approach-1:
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector < vector<int>> res;
vector <int> cur;
allSubsets(nums, cur, 0, res);
return res;
}
void allSubsets(vector<int>& v, vector<int>& cur, int idx, vector<vector<int>>& res) {
if (idx == v.size()) {
res.emplace_back(cur);
return;
}
allSubsets(v, cur, idx+1, res);
cur.emplace_back(v[idx]);
allSubsets(v, cur, idx+1, res);
cur.pop_back();
}
};
This approach above of recursive backtracking is understandable due to the reasoning that for every element we are considering two paths-- 1 with elements included and the 2nd with element excluded.
But I recently saw this following backtracking approach to do the same (generate all subsets), which doesn't make sense to me. It doesn't seem similar to above as genSets is being called a variable # of times within its body than exact 2 times in the previous approach.
approach-2:
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> subs;
vector<int> sub;
genSubsets(nums, 0, sub, subs);
return subs;
}
void genSubsets(vector<int>& nums, int start, vector<int>& sub, vector<vector<int>>& subs) {
subs.push_back(sub);
for (int i = start; i < nums.size(); i++) {
sub.push_back(nums[i]);
genSubsets(nums, i + 1, sub, subs);
sub.pop_back();
}
}
};
So how is it doing the same work? In 'genSubsets' where are subsets that exclude the current index being formed?
If nums was {1, 2, 3, 4}, where would the subset {1, 2, 3} get constructed as we don't call genSubsets are pop_back or before sub.push_back?
I've spent hours trying to understand this second approach with no luck and confused how it works and is similar to the approach-1 above?
Aucun commentaire:
Enregistrer un commentaire