回溯法

概述

回溯法提供了一种暴力搜索的手段，关键在于状态的演变以及复位，比如:

1. 本状态是A, 可能走到的状态集合为{B, C, D};
2. 先保留状态A所在的环境，然后进行到状态B处理;
3. 回溯回状态A, 并且复位上下文,接着处理状态C,依次类推，处理完所有剩余的状态。

题目

Restore IP Addresses

要求

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)

实现代码如下：

class Solution {
public:
    int strtoint(string s) {
        int ret;
        stringstream ss(s);
        ss >> ret;
        return ret;
    }
    
    void search(vector<string>&result, string& candidate, string& s, int offset, int left_num) {
        if (left_num == 1) {
            if (offset == s.length()) {
                return;
            }
            
            string left_str = s.substr(offset);
            if (left_str[0] == '0' && left_str.length() > 1) {
                return;
            }
            
            int left_int = strtoint(left_str);
            if (left_int <= 255) {
                candidate += left_str;
                result.push_back(candidate);
            }
            return;
        }
        
        int search_len = 3;
        if (s[offset] == '0') {
            search_len = 1;
        }
        
        for (int i = 1; i <= search_len; ++i) {
            if ( i + offset >= s.length()) {
                continue;
            }
            
            string next = s.substr(offset, i);
            
            int cur_cand_len = candidate.length();
            if (i <= 2 || (i == 3 && strtoint(next) <= 255)) {
                candidate += next;
                candidate += ".";
                search(result, candidate, s, offset + i, left_num - 1);
            }
            candidate.resize(cur_cand_len);
        }
    }
    
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        string candidate = "";
        search(result, candidate, s, 0, 4);
        return result;
    }
};

Permutations

Given a collection of distinct numbers, return all possible permutations.

典型的回溯法， 代码如下：

class Solution {
public:

    void search(vector<vector<int>>& result, vector<int>& one_perm, vector<int>&nums, int begin) {
        if (nums.size() == begin) {
            result.push_back(one_perm);
            return;
        }
        for (int i = begin; i < nums.size(); ++i) {
            swap(nums[i], nums[begin]);
            one_perm.push_back(nums[begin]);
            search(result, one_perm, nums, begin + 1);
            swap(nums[i], nums[begin]);
            one_perm.pop_back();
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        if (nums.size() == 0) {
            return result;
        }
        vector<int> one_perm;
        search(result, one_perm, nums, 0);
        return result;
    }
};