8.7 dfs: restoreIP && co

to do

10.6] Restore IP Addresses

note 0.xx.0.xx is ok while 0x.xx.. is not)
// wrong move: placed starti+len+1

    int MAXCT = 4;
    void dfs(vector<string>& ret, string path, int segCt, const string& s, int starti) {
        if (segCt == MAXCT) {
            if (path.size() == s.size()+ MAXCT) {
                path.pop_back();
                ret.push_back(path);
            } 
            return;
        }
        // trim
        int remainingCt = s.size()-starti;
        if (remainingCt < (MAXCT-segCt) || remainingCt > (MAXCT-segCt)*3) return;
        
        // string [starti, starti+len)
        for (int len=1; len<=3 && starti+len<=s.size(); ++len) {
            string seg = s.substr(starti, len);
            if (stoi(seg)>255 || (seg[0]=='0' && seg.size()>1)) break;
            dfs(ret, path + seg + ".", segCt+1, s, starti+len); // wrong move: placed `starti+len+1`
        }
    }
    //  four decimal numbers, each ranging from 0 to 255 (note 0.xx.0.xx is ok while 0x.xx.. is not)
    vector<string> restoreIpAddresses(string s) {
        vector<string> ret;
        string path;
        dfs(ret, path, 0, s, 0);
        return ret;
    }

10.7] Combination Sum

note to keep non-desc order

    void dfs(vector<vector<int>>& ret, vector<int>& path, int starti, vector<int>& candidates, int target) {
        if (!target) {
            ret.push_back(path);
            return;
        }
        for (int i=starti; i<candidates.size(); ++i) {
            if (target-candidates[i]<0) break;
            path.push_back(candidates[i]);
            dfs(ret, path, i, candidates, target-candidates[i]);
            path.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> ret;
        vector<int> path;
        dfs(ret, path, 0, candidates, target);
        return ret;
    }

10.8] Combination Sum II

note how to avoid duplicate

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