---
# System prepended metadata

title: Recursive
tags: [Study_aboard]

---

# Recursive 
###### tags: `Study_aboard`

## Subsets I 

![](https://i.imgur.com/POZYLdD.png)




Easy one

```cpp 
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        
        vector<vector<int>> res; 
        vector<int> new_vector;
        
        if(nums.size()<=0){
            vector<int> empty;
            res.push_back(empty);
            return res;
        }
        
        new_vector = vector<int>(nums.begin(),nums.end()-1);
        vector<vector<int>> subres = subsets(new_vector);
        
        for(int i=0;i<subres.size();i++){ 
            res.push_back(subres[i]);   // do not add nums.end()
            subres[i].push_back(nums[nums.size()-1]);
            res.push_back(subres[i]);    // add nums.end()
        }
        return res;    
    }
};
```

## ==Subsets II==    

![](https://i.imgur.com/UrJl0hL.png)

1. 查詢是否重複做過數字
2. 若重複則只做 (current_size-old_generate_size) 
3. 用for loop 取代 recursive 比較容易記住前一次的數值


```cpp 
class Solution {
public:

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    
        // initialize res
        vector<vector<int>> res; 
        vector<int> empty; 
        res.push_back(empty);
        
        // last size record the size last done
        int last_size=0; 
        
        sort(nums.begin(), nums.end());
        
        for(int i=0;i<nums.size();i++){
            
            if(i==0 || nums[i]!=nums[i-1]){ // not duplicate 
                last_size = res.size();
                for(int j=0;j<last_size;j++){
                    vector<int> temp = res[j];
                    temp.push_back(nums[i]);
                    res.push_back(temp);
                }
            }
            else{   // duplicate
                int j=last_size;
                last_size = res.size();
                for( j=j ;j<last_size;j++){
                    vector<int> temp = res[j];
                    temp.push_back(nums[i]);
                    res.push_back(temp);
                }
            }
        }
        return res;
    }
};
```

## Combinations

![](https://i.imgur.com/yXTLgQH.png)

1. Method 1 : recursive way, think by myself

```cpp 
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        
        vector <vector<int>> res; 
        
        if(k==0){
            vector <int> empty;
            res.push_back(empty);
            return res;
        }
        
        if(n==1){
            vector<int> temp;
            temp.push_back(1);
            res.push_back(temp);
            return res;
        }
        
        
        for(int i=n;i>=k;i--){
            vector <vector<int>> sub_combine = combine(i-1, k-1);
            
            for(int j=0;j<sub_combine.size();j++){
                sub_combine[j].push_back(i);
                res.push_back(sub_combine[j]);
            }
        }
        
        return res;
    }
};
```
2. Method 2


## Letter Combinations of a Phone number

1. DFS 

```cpp 
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        
        vector<vector<char>> d(10);
        d[0] = {' '};
        d[1] = {};
        d[2] = {'a','b','c'};
        d[3] = {'d','e','f'};
        d[4] = {'g','h','i'};
        d[5] = {'j','k','l'};
        d[6] = {'m','n','o'};
        d[7] = {'p','q','r','s'};
        d[8] = {'t','u','v'};
        d[9] = {'w','x','y','z'};
        string cur;
        vector<string> ans;
        dfs(digits, d, 0, cur, ans);
        return ans;
    }
private:
    void dfs(string digits,vector<vector<char>>& d, int l, string cur, vector<string>& ans ){
        
        // l is which digit recursively using now
        if(l==digits.length()){
            ans.push_back(cur);
            return ;
        }
        
        for(const char c: d[digits[l]-'0']){
            cur.push_back(c);
            dfs(digits, d, l+1, cur, ans);
            cur.pop_back();
        }
    }
};
```

2. BFS
```cpp
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        
        vector<vector<char>> d(10);
        d[0] = {' '};
        d[1] = {};
        d[2] = {'a','b','c'};
        d[3] = {'d','e','f'};
        d[4] = {'g','h','i'};
        d[5] = {'j','k','l'};
        d[6] = {'m','n','o'};
        d[7] = {'p','q','r','s'};
        d[8] = {'t','u','v'};
        d[9] = {'w','x','y','z'};
        string cur;
        vector<string> ans{""};
        
        for(char digit:digits){
            vector<string> temp;
            for(string s: ans){
                for(char c: d[digit-'0']){
                    temp.push_back(s+c);
                }
            }
            
            ans.swap(temp);
        }
        
        return ans;
    }
};
```
## Permutations 
![](https://i.imgur.com/GvEUGk7.png)
Initial: 想法跟下圖一樣
![](https://i.imgur.com/bDls4wZ.png)



```cpp 
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        
        if(nums.empty()){
            return vector<vector<int>>(1, vector<int>());
        } 
        
        vector<vector<int>> res;
        int cur = nums[nums.size()-1];
        nums.pop_back();
        vector<vector<int>> temp_res = permute(nums);
        
        for(auto &v : temp_res){
            for(int i=0;i<=v.size();i++){
                v.insert(v.begin()+i,cur);
                res.push_back(v);
                v.erase(v.begin()+i);
            }
        }
        return res;
    }
};
```
## Permutations II 
![](https://i.imgur.com/nbK6sH8.png)
==Hard for me==
Initial: No thoughts
Problem: cannot solve duplicates
Solution: 

Don't like duplicates -> try to change the elements to unique
Use hashmap to record unique elements and counts
![](https://i.imgur.com/eLiQeJc.jpg)

```cpp 
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
    vector<vector<int>> v;
    vector<int> r;
    map<int, int> map;
    for (int i : num)
    {
        if (map.find(i) == map.end()) map[i] = 0;
        map[i]++;
    }
    permuteUnique(v, r, map, num.size());
    return v;
}

void permuteUnique(vector<vector<int>> &v, vector<int> &r, map<int, int> &map, int n)
{
    if (n <= 0)
    {
        v.push_back(r);
        return;
    }
    for (auto &p : map)
    {
        if (p.second <= 0) continue;
        p.second--;
        r.push_back(p.first);
        permuteUnique(v, r, map, n - 1);
        r.pop_back();
        p.second++;
    }
}
};
```
## Pow(x,n) ==Facebook==
![](https://i.imgur.com/rsQJtsa.png)

```Initial``` use while loop to calculate
```Problem``` TLE
```Solution``` Use recursive to break pow n to pow n/2
```cpp 
class Solution {
public:
    double myPow(double x, int n) {
        
        if(!n || x==1) return 1;
        if(x==-1) return n%2?-1:1;
        if(n==-1) return 1/x;
        if(n==1) return x;
        double half = myPow(x, n / 2);
        return half * half * myPow(x,n%2);

    }
};

```
## Word Break

![](https://i.imgur.com/HkG5OMz.png)




```cpp
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        // Unordered sets are containers that store unique elements in no particular order, and which allow for fast retrieval of individual elements based on their value.
        
        vector<bool> dp(s.size() + 1);
        
        dp[0] = true; // " " is always true
        
        for (int i = 0; i < dp.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordSet.count(s.substr(j, i - j))>0 ) {  
                    // unordered_set.count : count elements with specific value
                    // string substr (size_t pos = 0, size_t len = npos)
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp.back();
    }
};
```

## World break II 

![](https://i.imgur.com/wkczqpN.png)

==列舉所有可能的題目，想到recursive==

```cpp
class Solution {
public:
    
    unordered_map<string, vector<string>> m;
    
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        
        if (s.empty()) 
            return {""};
        
        if (m.count(s)) // already done do not need to do again
            return m[s];
        
        vector<string> res;
        
        for (string word : wordDict) {
            
            if(s.substr(0,word.size())!=word)
                continue;
            
            vector<string> temp;
            temp = wordBreak(s.substr(word.size()) , wordDict);
            
            for(auto str : temp){
                res.push_back(word + ((str=="")?"":" ") + str);
            }
        }
        
        m[s] = res;
        return res;
    }
};
```
## Word Ladder
![](https://i.imgur.com/jRetCx0.png)


Initial: 想要無腦使用DFS
problem: ==DFS並不會出現optimal solution==
ultimate: use BFS

iterative solution
```cpp 
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        
        if (!wordSet.count(endWord)) return 0; // no endword in wordList
        
        unordered_map<string, int> pathCnt{{{beginWord, 1}}}; // string and count
        queue<string> q{{beginWord}}; // bfs queue
        
        while (!q.empty()) {
            string word = q.front(); q.pop();
            for (int i = 0; i < word.size(); ++i) { // search from a~z for each position in the word
                string newWord = word;
                for (char ch = 'a'; ch <= 'z'; ++ch) {
                    newWord[i] = ch;
                    if (wordSet.count(newWord) && newWord == endWord) return pathCnt[word] + 1;
                    if (wordSet.count(newWord) && !pathCnt.count(newWord)) {
                        q.push(newWord);
                        pathCnt[newWord] = pathCnt[word] + 1;
                    }   
                }
            }
        }
        return 0;
    }
};
```

recursive solution
==2-end BFS== will be faster than 1-end BFS in many cases (but time complexity is not better)
do BFS from end and front at the same time
```cpp 
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> s1, s2, wlist;
        s1.insert(beginWord);
        s2.insert(endWord);
        for(string w : wordList){
            wlist.insert(w);
        }
        if(wlist.count(endWord) == 0){
            return 0;
        }
        return find(s1, s2, wlist, 0);
    }
    
    int find(unordered_set<string>& s1, unordered_set<string>& s2, unordered_set<string>& wlist, int len){
        
        unordered_set<string> next; // bfs queue in this round
        for(string s : s1){
            wlist.erase(s); // avoid duplicate
            
            // 2-end BFS
            if(s2.count(s) > 0){    // another end already got s in s1
                return len + 1;
            }
            
            for(int i = 0; i < s.length(); ++i){
                char cur = s[i];
                for(char c = 'a'; c <='z'; ++c){
                    if(c == cur){
                        continue;
                    }
                    s[i] = c;
                    if(wlist.count(s) > 0){
                        next.insert(s);
                    }
                    s[i] = cur;  
                }
            }
        }
        s1 = next;
        if(s1.empty()){
            return 0;
        }
        // 先做size小的
        if(s2.size() < s1.size()){
            return find(s2, s1, wlist, len + 1);
        }
        return find(s1, s2, wlist, len + 1);
    }
};
```
## Word Ladder II 
![](https://i.imgur.com/yczRa4z.png)
![](https://i.imgur.com/tv6Ztjr.png)

similar to word ladder I, but we use a vector<string> in the queue.

```cpp 
class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordlist) {
        
        vector<vector<string>> res; 
        
        unordered_set <string> visited;
        
        queue<vector<string>> q;
        
        q.push({beginWord}); // watch out the syntax
        
        unordered_set<string> wordList (wordlist.begin(), wordlist.end());
        
        int level = 1; // res 的長度
        
        bool find = false;
        
        if(wordList.find(endWord)==wordList.end()){
            return res;
        }
        
        while(!q.empty()){
            
            
            vector<string> cur;
            cur = q.front();
            
            if(cur.size()>level && find==true){
                return res;
            }
            else if(cur.size()>level && find==false){
                level = cur.size();
                // 上層若已經使用過，下層使用所得的solution必會較差，因此我們可以直接erase it
                for (string w : visited) wordList.erase(w);
                visited.clear();
            }
            
            q.pop();
            
            string cur_last = cur.back();
            
            for(int i=0;i<cur_last.size();i++){
                
                for(char c='a'; c<='z';c++){
                    
                    string new_cur_last = cur_last;
                    new_cur_last[i] = c;
                    
                    if(wordList.find(new_cur_last)!=wordList.end()){
                        vector<string> new_cur = cur;
                        new_cur.push_back(new_cur_last);
                        visited.insert(new_cur_last);
                        
                        if(new_cur_last==endWord){
                            res.push_back(new_cur);
                            find = true;
                        }
                        
                        else{
                            q.push(new_cur);
                        }
                    }
                    
                }
                
            } 
        }
        return res;
    }
};
```
