回溯算法

括号生成

给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

vector<string> generate(int n){
  vector<string> result;
  helper(0, 0, "", result, n);
}

void helper(int left, int right, string out, vector<string>& result){
  if(left < 0 || right < 0 || left > right) return;
  if(left == 0 && right == 0){    //保持左右一致，且左边在前
      result.push_back(out);
      return;
  }
  helper(left-1, right, out+"(", result);
  helper(left, right-1, out+")", result);
}

全排列1-2

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

//没有重复时，用set即可
 vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        int n=nums.size();
        helper(nums, 0, n-1, res);
        return res;
    }
    
    void helper(vector<int>& a, int left,int right, vector<vector<int>> &res){
        if (left==right) {res.push_back(a);return;}
        for (int i=left; i<=right; ++i){
            swap(a[i], a[left]);
            helper(a,left+1,right,res);
            swap(a[i], a[left]);
        }
    }

子集1-2

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

//不要重复，用set代替vector
    vector<vector<int> > subsets(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int> > result;
        vector<int> res;
        helper(nums,res,result,0);
        return result;
    }  
    void helper(vector<int>& nums, vector<int>& res, vector<vector<int> >& result, int i){
        result.push_back(res);
        for(;i<nums.size();++i){    
            res.push_back(nums[i]);  
            helper(nums, res, result, i+1);
            res.pop_back();
        }
    } 

[组合总和1-2]

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

//这一题也可以用指针来计算
vector<vector<int>> combi(vector<int>& nums, int target){
  vector<vector<int>> result;
  vector<int> res;
  sort(nums.begin(), nums.end());
  helper( nums, 0, target, res, result);
  return result;
}
void helper(vector<int>& nums, int start, int target, vector<int>& res, vector<vector<int>>& result){
  if(target < 0) return;
  if(target == 0) {
      result.push_back(res);
      return;
  }
  for(int i=start; i<nums.size(); ++i){
     //if(nums[i] == nums[i-1] && i>start) continue;    //不要重复的
    res.push_back(nums[i]);
    helper(nums, i, target-nums[i], res, result);
    res.pop_back();
  }
}

分割回文串

输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]

vector<vector<string>> partition(string s){
  vector<vector<string>> result;
  vector<string> res;
  helper(res, result, s, 0);
  return result;
}
void helper(vector<string>& res, vector<vector<string>>& result, string s, int start){
  if(start>=s.size()) {
    result.push_back(res);  
    return;
  }
  for(int i=start;i<s.size();i++){
    int l=start;
    int r=i;
    while(s[l]==s[r] && l<=r){ l--;r++;}
    if(l>=r){
        res.push_back(s.substr(start, i-start+1));
        helper(s, i+1, res, result);
        res.pop_back();
    }
  }

}

复原ip地址

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        helper(s, 0, "", res);
        return res;
    }
    
    void helper(string s, int n, string out, vector<string>& res){
        if(n==4){
            if (s.empty()) res.push_back(out);
            return;
        }
            for(int k=1;k<4;++k){  //每一个最多3位数
                if(s.size() < k) break;
                int val = atoi(s.substr(0,k).c_str());
                if (val > 255 || k!=to_string(val).size()) continue;
                helper(s.substr(k), n+1, out+s.substr(0,k)+(n==3?"":"."), res);
            
        }
    }

单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

 bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (search(board, word, 0, i, j, visited)) return true;
            }
        }
        return false;
    }
    bool search(vector<vector<char>>& board, string word, int idx, int i, int j, vector<vector<bool>>& visited) {
        if (idx == word.size()) return true;
        int m = board.size(), n = board[0].size();
        if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != word[idx]) return false;
        visited[i][j] = true;
        bool res = search(board, word, idx + 1, i - 1, j, visited) 
                 || search(board, word, idx + 1, i + 1, j, visited)
                 || search(board, word, idx + 1, i, j - 1, visited)
                 || search(board, word, idx + 1, i, j + 1, visited);
        visited[i][j] = false;
        return res;
    }

电话号码的组合

void helper (string digits, vector<string>& vec, string res, vector<string>& result){
    if (digits.length() == 0){
        result.push_back(res);
    }else{
        string digit = digits.substr(0,1);
        int num = atoi(digit.c_str());
        //int num = digits[0] - '0';
        string letters = vec[num-2];
        for(int i = 0; i < letters.length(); i++){
            string letter = letters.substr(i,i+1);
            helper(digits.substr(1), vec, res+letter, result);
        }  
    }
}     
vector<string> letterCombinations(string digits, vector<string>& vec) {
    vector<string> result;
    if (digits.length() != 0)
     helper(digits, vec, "", result);
    return result;  
}
     
int main(){
    string s[]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> vec(s,s+sizeof(s)/sizeof(string));
    string digits="23";
    vector<string> result = letterCombinations(digits, vec);
}

通配符匹配

正则表达式匹配