7.19 subsetII & nextPermutat

to do

subset还有其他做法，下遍看

1] Subsets II

1. recursive

    void subsetsR(vector<int>& nums, int lastAppendeeI, int lastAppendS, vector<vector<int>>& ret) {
        if (lastAppendeeI+1 >= nums.size()) return;
        int newN = nums[lastAppendeeI+1];
        int start = lastAppendeeI>-1 && (newN==nums[lastAppendeeI]) ? lastAppendS : 0;
        int end = ret.size(); 
        for (int i=start; i<end; ++i) {
            vector<int> v = ret[i];
            v.push_back(newN);
            ret.push_back(v);
        }
        subsetsR(nums, ++lastAppendeeI, end, ret);
    }
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret={{}};
        subsetsR(nums, -1, 0, ret);
        return ret;
    }

2. iterative

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret = {{}};
        int lastAppendS = 0;
        for (int i=0; i<nums.size(); ++i) {
            int newN=nums[i];
            int retS = ret.size(); 
            int start = (i && newN==nums[i-1])? lastAppendS : 0;
            lastAppendS = retS;
            for (int j=start; j<retS; ++j) {
                vector<int> v = ret[j];
                v.push_back(newN);
                ret.push_back(v);
            }
        }
        return ret;
    }

reconsider w/ backtracking
回头看答案的backtracking, 画了图比较清楚的理了思路，recursion version正确打开方式：

reference: subset sum

• With nums of size N, we have 2^N different subsets.
• Every leave node indicates end of exploration, hence out put this path then backtrack to previous state.
• Every non-leave node P owns two branches: rb contains nums[p's level] while lb doesn't.

Redo subset w/ recursion

    void subsetsR(vector<int>& nums, vector<int>& path, int level, vector<vector<int>>& ret) {
        if (level == nums.size()) {
            ret.push_back(path);
            return;
        }
        
        subsetsR(nums, path, level+1, ret);
        path.push_back(nums[level]);
        subsetsR(nums, path, level+1, ret);
        path.pop_back();
        return;
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> path;
        vector<vector<int>> ret;
        subsetsR(nums, path, 0, ret);
        return ret;
    }

subset w/ dups

马克： 下面一句还不十分理解。。
这题有重复元素，但本质上，跟上一题很类似，上一题中元素没有重复，相当于每个元素只能
选0 或1 次，这里扩充到了每个元素可以选0 到若干次而已

    void dfs(vector<int>& nums, vector<int>& path, int start, vector<vector<int>>& ret) {
        ret.push_back(path);
        
        for (int i=start; i<nums.size(); ++i) {
            if (i!=start && nums[i]==nums[i-1]) continue;
            path.push_back(nums[i]);
            dfs(nums, path, start+1, ret);
            path.pop_back();
        }
    }
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> path; 
        vector<vector<int>> ret;
        dfs(nums, path, 0, ret);
        return ret;
    }

figure out why seg fault

    vector<vector<int>> permute(vector<int>& nums) {
        if (nums.empty()) return vector<vector<int>> {};
        if (nums.size()==1) return vector<vector<int>> {{nums[0]}};
        
        vector<vector<int>> ret;
        vector<int>* lastNums = new vector<int>(nums.begin()+1, nums.end());
        auto lastRet = permute(*lastNums);
        int newNum = *(nums.begin());
        
        for (auto& v: lastRet) {
            for (auto pos=v.begin(); pos<=v.end(); ++pos) {
                auto newv = v;
                cout<<*pos<<"kk";
                newv.insert(pos, newNum);
                ret.push_back(newv);
            }
        }
        return ret;
    }

Permutations

很低级的bug。。强行v1.insert(v2的iterator, val) ：（

• method 1: recursion

    vector<vector<int>> permute(vector<int>& nums) {
        if (nums.empty()) return vector<vector<int>> {};
        if (nums.size()==1) return vector<vector<int>> {{nums[0]}};
        
        vector<vector<int>> ret;
        int newNum = *(nums.end()-1);
        vector<int> lastNums(nums.begin(), nums.end()-1);
        auto lastRet = permute(lastNums);
        
        for (auto& v: lastRet) {
            for (auto pos=0; pos<=v.size(); ++pos) {
                vector<int> newv = v;
                newv.insert(newv.begin()+pos, newNum);
                ret.push_back(newv);
            }
        }
        return ret;
    }

• **method 2: better recursion **(see tree)
  Permutations
  仔细想了写
  

    void dfs(vector<int>& nums, vector<int>& path, vector<vector<int>>& ret) {
        if (path.size()==nums.size()) {
            ret.push_back(path);
            return;
        }
        for (int i: nums) {
            if (find(path.begin(), path.end(), i) == path.end()) {
                path.push_back(i);
                dfs(nums, path, ret);
                path.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        vector<vector<int>> ret;
        dfs(nums, path, ret);
        return ret;
    }