lincode 680 Split String

Split String 

•  描述
•  筆記
•  數據
•  評測

Give a string, you can choose to split the string after one character or two adjacent characters, and make the string to be composed of only one character or two characters. Output all possible results.

Given the string "123"
return [["1","2","3"],["12","3"],["1","23"]]

這道題目剛一開始我想的就是 第一點，可後來發現並不需要。現在感覺能用void就用void，過多的返回值不暈才怪。

1.看到題目給定的函數返回類型是一個嵌套vector，所以很容易的會想到另外設計一個解決函數且返回類型是vector。

2.回溯法的題目必定需要恢復現場，這道題目要考慮的就是怎麼恢復現場。

3.考慮嵌套vector什麼時候進行插入，考慮插入條件。

4.註意當s.size()==0時怎麼操作

下麵是沒有進行再次優化的代碼，有錯誤或者改進請大佬指出。

class Solution {
public:
    /*
     * @param : a string to be split
     * @return: all possible split string array
     */
    vector <string> a;
    vector<vector<string> > ans;
    void back(int t,int n,string &s)
    {
        if(!s.size())
            {
                ans.push_back(a);
                return ;
            }
        if(t>=s.size())     
        　　return ;
        else{
            if(n==1){
                string c="";
                c=c+s[t];
                a.push_back(c);
                if(t+1==s.size()){
                    ans.push_back(a);
                }
                t++;
                back(t,1,s);
                t++;
                back(t,2,s);
                t-=2;
                a.erase(a.end()-1);
            }
            else{
                string c="";
                c=c+s[t-1]+s[t];
                a.push_back(c);
                if(t+1==s.size()){
                    ans.push_back(a);
                }
                t++;
                back(t,1,s);
                t++;
                back(t,2,s);
                t-=2;
                a.erase(a.end()-1);
            }
            
            
        }
    return ;    
    }
    vector<vector<string> > splitString(string& s) {
        // write your code here
        
        back(0,1,s);
        if(s.size()>1)
            back(1,2,s);
        return ans;
    }
};