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

## Subsets I


Easy one

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==


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

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


1. Method 1 : recursive way, think by myself

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

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

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
Initial: 想法跟下圖一樣

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
==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

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==

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)

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==

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

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

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.

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;
}
};