leetcode几个可以用回溯的小题er

回溯：简单来说从一条路往前走，走不通再回来，换一条路走。
以深度优先（dfs）方式搜索解空间

1. 括号生成

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

vector<string> generateParenthesis(int n) {
    vector<string> vec;
    int left = n, right = n;
    string str = "";
    dfs(vec, str, left, right);
    return vec;
}


void dfs(vector<string>& vec, string str, int left, int right) {
    if (0 == left && 0 == right) {
        vec.push_back(str);
        return;
    }
    if (left > 0) {
        dfs(vec, str + '(', left - 1, right);
    }
    if (right > 0 && left < right) {
        dfs(vec, str + ')', left, right - 1);
    }
}

一眼就能看出来用 dfs。没有技巧，熟能生巧。

2. ip转换

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given"25525511135",
return["255.255.11.135", "255.255.111.35"]. (Order does not matter)

vector<string> restoreIpAddresses(string s) {
    string temp = "";
    int count = 0;
    vector<string> res;
    DFS(res, s, temp, count);
    return res;
}

void DFS(vector<string>& res, const string& s, const string& temp, int count)
{
    if (count == 3) {
        if (isValid(s)) {
            res.push_back(temp + s);
        }
        return;
    }
    for (int i = 1; i < 4 && i < s.size(); ++i)
    {
        string sub = s.substr(0, i);
        if (isValid(sub))
        {
            DFS(res, s.substr(i), temp + sub + '.', count + 1);
        }
    }
}

bool isValid(const string& str)
{
    int num = atoi(str.c_str());
    if (str.size() > 1)
    {
        return str[0] != '0' && 0 <= num && num <= 255;
    }
    return 0 <= num && num <= 255;
}

3. 找子集

Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S =[1,2,2], a solution is:
[↵ [2],↵ [1],↵ [1,2,2],↵ [2,2],↵ [1,2],↵ []↵]

vector<vector<int> > subsetsWithDup(vector<int>& S) {
    sort(S.begin(), S.end());
    vector<vector<int> > res;
    vector<int> temp;
    DFS(S, 0, res, temp);
    return res;
}

void DFS(vector<int>& set, int start, vector<vector<int> >& res, vector<int>& temp)
{
    res.push_back(temp);
    for (int i = start; i < set.size(); ++i)
    {
        temp.push_back(set[i]);
        DFS(set, i + 1, res, temp);
        while (i < set.size() - 1 && set[i] == set[i + 1])
        {
            ++i;
        }
        temp.pop_back();
    }
}

ps：用 dfs 解题形式都差不多，重在理解。