lundi 19 février 2018

There seem to be at least 2 ways to do backtracking, How does this specific approach of backtracking really work?

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