目錄
- 七、遞歸和回溯
- 1、回溯
- 2、回溯應用 - 排列問題
- 2、回溯應用 - 組合問題
- 3、回溯應用 - 二維平面
- 4、回溯應用 - floodfill算法 問題
- 4、回溯應用 - 搜索問題 - 八皇后
- 參考
七、遞歸和回溯
- 結局問題的思路普遍還是樹形問題；
- 寫遞歸的時候，心里要有一個遞歸樹
- 遞歸調用嘗試找答案的問題稱作回溯
1、回溯
17. 電話號碼的字母組合
- 這種題沒什么意義，不用復習 O(3^n) = O(2 ^n）指數級；
class Solution {
public:vector
<vector
<char>> map
;void dfs(string
&digits
,int index
,vector
<string
> &res
,string str
){if(index
>digits
.size()) return;if(index
== digits
.size()){if(str
!="")res
.push_back(str
);return;}int index_m
= digits
[index
]-'2';for(int i
=0;i
<map
[index_m
].size();i
++)dfs(digits
,index
+1,res
,str
+map
[index_m
][i
]);}vector
<string
> letterCombinations(string digits
) {vector
<string
> res
;map
= {{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};dfs(digits
,0,res
,"");return res
;}
};
93. 復原 IP 地址
class Solution {
public:vector
<string
> res
;void dfs(const string
& s
,int index
,int nums
,string str
){if(nums
==4&&index
==s
.size()){res
.push_back(str
.substr(0,str
.size()-1));return ;}if(index
>=s
.size()) return ;if(nums
>3) return;int temp2
= stoi(s
.substr(index
,2));int temp3
= stoi(s
.substr(index
,3));dfs(s
,index
+1,nums
+1,str
+s
[index
]+".");if(s
[index
]!='0')dfs(s
,index
+2,nums
+1,str
+s
.substr(index
,2)+".");if(s
[index
]!='0'&& temp3
>0&&temp3
<256)dfs(s
,index
+3,nums
+1,str
+s
.substr(index
,3)+".");}vector
<string
> restoreIpAddresses(string s
) {dfs(s
,0,0,"");return res
;}
};
131. 分割回文串
- dfs 回溯；對于判斷回文，可以用記憶化，算的時候，記下來那部分算過；
class Solution {
private:bool ispalindrome(const string
&str
){for (int i
= 0, j
= str
.size()-1; i
< j
; i
++,j
--)if (str
[i
] != str
[j
])return false;return true;}void dfs(string
&s
, int index
, vector
<string
> &temp
){if (index
== s
.size())res
.push_back(temp
);if (index
>= s
.size()) return;for (int i
= index
; i
< s
.size(); i
++){string m_str
= s
.substr(index
, i
- index
+ 1);if (ispalindrome(m_str
)){temp
.push_back(m_str
);dfs(s
, i
+ 1, temp
);temp
.pop_back();}}}vector
<vector
<string
>> res
;
public:vector
<vector
<string
>> partition(string s
) {vector
<string
> temp
;dfs(s
, 0,temp
);return res
;}
};
2、回溯應用 - 排列問題
46. 全排列
class Solution {
public:vector
<vector
<int>> res
;vector
<bool> mash_
;void dfs(const vector
<int>& nums
,vector
<int>& temp
,int index
){if(index
== nums
.size()){res
.push_back(temp
);return ;}for(int i
=0;i
<nums
.size();i
++){if(!mash_
[i
]){mash_
[i
] =true;temp
[index
] = (nums
[i
]);dfs(nums
,temp
,index
+1);mash_
[i
] = false;}}}vector
<vector
<int>> permute(vector
<int>& nums
) {mash_
= vector
<bool>(nums
.size(),false);vector
<int> temp(nums
.size(),0);dfs(nums
,temp
,0);return res
;}
};
47. 全排列 II
- 相對上面的，加上了用hashset 記錄當前index用過的數字
- 或者直接判斷和上一個一不一樣；一樣就跳過
class Solution {
public:vector
<unordered_set
<int>> _hash
;vector
<vector
<int>> res
;vector
<bool> _hash_bo
;void dfs(vector
<int>& nums
,int index
,vector
<int>& temp
){if(index
==nums
.size()){res
.push_back(temp
);return;}for(int i
= 0;i
<nums
.size();i
++){if(!_hash_bo
[i
]){if(_hash
[index
].find(nums
[i
]) == _hash
[index
].end()){temp
[index
] = nums
[i
];_hash
[index
].insert(nums
[i
]);_hash_bo
[i
] = true;dfs(nums
,index
+1,temp
);_hash_bo
[i
] = false;}}}_hash
[index
].clear();}vector
<vector
<int>> permuteUnique(vector
<int>& nums
) {_hash
= vector
<unordered_set
<int>>(nums
.size());vector
<int> temp(nums
.size());_hash_bo
= vector
<bool>(nums
.size(),false);dfs(nums
,0,temp
);return res
;}
};
2、回溯應用 - 組合問題
77. 組合
class Solution {
public:void dfs(vector
<int> &temp
,int index
,const int nums
,const int &n
,const int & k
) {if(index
==k
) res
.push_back(temp
);if(index
>=k
) return;if(k
-index
-1>n
-nums
) return;for(int i
=nums
;i
<=n
;i
++){temp
[index
] = i
;dfs(temp
,index
+1,i
+1,n
,k
);}}vector
<vector
<int>> res
;vector
<vector
<int>> combine(int n
, int k
) {vector
<int> temp(k
,0);dfs(temp
,0,1,n
,k
);return res
;}
};
39. 組合總和
- 回溯、剪枝；但是為了不能重復 ；所以索引和之前的索引一致
class Solution {
public:vector
<vector
<int>> res
;vector
<int> temp
;void dfs(vector
<int>& candidates
,const int& target
,int sum
,int index
){if(sum
==target
) {res
.push_back(temp
);return ;}if(index
>=candidates
.size()) return ;for(int i
=index
;i
<candidates
.size();i
++){if(sum
+candidates
[i
]<=target
){temp
.push_back(candidates
[i
]);dfs(candidates
,target
,sum
+candidates
[i
],i
);temp
.pop_back();}}}vector
<vector
<int>> combinationSum(vector
<int>& candidates
, int target
) {dfs(candidates
,target
,0,0);return res
;}
};
40. 組合總和 II
- 回溯、剪枝；但是為了不能重復 ；所以哈希做一下這一位不能用之前用過的
- 或者用判斷和前一個一不一樣即可；
class Solution {
public:vector
<vector
<int>> res
;vector
<int> temp
;void dfs(vector
<int>& candidates
,const int& target
,int sum
,int index
){if(sum
==target
) {res
.push_back(temp
);return ;}if(index
>=candidates
.size()) return ;unordered_set
<int> _hash
;for(int i
=index
;i
<candidates
.size();i
++){if(sum
+candidates
[i
]<=target
&&_hash
.find(candidates
[i
])==_hash
.end()){_hash
.insert(candidates
[i
]);temp
.push_back(candidates
[i
]);dfs(candidates
,target
,sum
+candidates
[i
],i
+1);temp
.pop_back();}}}vector
<vector
<int>> combinationSum2(vector
<int>& candidates
, int target
) {sort(candidates
.begin(),candidates
.end());dfs(candidates
,target
,0,0);return res
;}
};
216. 組合總和 III
class Solution {
public:vector
<vector
<int>> res
;vector
<int> temp
;void dfs(const int &k
,int index
,int n
,int i_vec
){if(index
==k
&& n
==0){res
.push_back(temp
);return;}if(index
>=k
) return ;for(int i
=i_vec
;i
<10;i
++){if(n
-i
>=0){temp
[index
] = i
;dfs(k
,index
+1,n
-i
,i
+1);}}}vector
<vector
<int>> combinationSum3(int k
, int n
) {temp
= vector
<int>(k
,0);dfs(k
,0,n
,1);return res
;}
};
78. 子集
class Solution {
public:vector
<int> temp
;vector
<vector
<int>> res
;void dfs(vector
<int>& nums
,int index
){if(index
== nums
.size()){res
.push_back(temp
);return;}dfs(nums
,index
+1);temp
.push_back(nums
[index
]);dfs(nums
,index
+1);temp
.pop_back();}vector
<vector
<int>> subsets(vector
<int>& nums
) {dfs(nums
,0);return res
;}
};
90. 子集 II 類似40. 組合總和 II
*
class Solution {
public:vector
<vector
<int>> res
;vector
<int> temp
;void dfs(vector
<int>& nums
,int index
,const int& len
){if(temp
.size() ==len
) {res
.push_back(temp
);return ;}for(int i
=index
;i
<nums
.size();i
++){if(i
==index
||(i
>index
&& nums
[i
]!= nums
[i
-1])){temp
.push_back(nums
[i
]);dfs(nums
,i
+1,len
);temp
.pop_back();}}}vector
<vector
<int>> subsetsWithDup(vector
<int>& nums
) {int len
= nums
.size();sort(nums
.begin(),nums
.end());for(int i
=0;i
<=len
;i
++)dfs(nums
,0,i
);return res
;}
};
- 按同層上次有沒有用到來dfs
- used_pre == false 代表同層 用過了，我這支分支就不能用了
- 也就是說，對于當前選擇的數 x，若前面有與其相同的數 y，且沒有選擇 y，此時包含 x 的子集，必然會出現在包含 y 的所有子集中。
- 和上面的方法，扔掉的分支相同；
class Solution {
public:vector
<vector
<int>> res
;vector
<int> temp
;void dfs(vector
<int>& nums
,int index
,bool used_pre
){if(index
==nums
.size()) {res
.push_back(temp
);return;}if(index
>=nums
.size()) return;dfs(nums
,index
+1,false);if((!used_pre
)&&index
>0&&nums
[index
] ==nums
[index
-1]) return ;temp
.push_back(nums
[index
]);dfs(nums
,index
+1,true);temp
.pop_back();}vector
<vector
<int>> subsetsWithDup(vector
<int>& nums
) {sort(nums
.begin(),nums
.end());dfs(nums
,0,false);return res
;}
};
401. 二進制手表 //*
class Solution {
public:vector
<string
> res
;void result_cal(pair
<int,int> nums
){if(nums
.first
>11) return;if(nums
.second
>59) return;string _l
= to_string(nums
.first
);_l
+=":";if(nums
.second
<10) _l
+= "0";_l
+= to_string(nums
.second
);res
.push_back(_l
);}void dfs(int turnedOn
,int index
,pair
<int,int> nums
){if(index
==10&& turnedOn
==0){result_cal(nums
);return;}if(index
>=10) return;dfs(turnedOn
,index
+1,nums
);if(turnedOn
>0){if(index
<6)nums
.second
+=1<<index
;elsenums
.first
+=1<<(index
-6);dfs(turnedOn
-1,index
+1,nums
);if(index
<6)nums
.second
^=1<<index
;elsenums
.first
^=1<<(index
-6);}}vector
<string
> readBinaryWatch(int turnedOn
) {dfs(turnedOn
,0,{0,0});return res
;}
};
3、回溯應用 - 二維平面
79. 單詞搜索
- 暴力dfs + 預處理；
- 遞歸中經典的先污染后治理方案；
class Solution {
public:vector
<vector
<bool>> _used
;bool dfs(vector
<vector
<char>>& board
, string word
,int word_index
,int x
,int y
){if(x
<0||y
<0||x
>=board
[0].size()||y
>=board
.size()) return false;if(_used
[y
][x
]) return false;if(word_index
>=word
.size()) return false;if(board
[y
][x
]!=word
[word_index
]) return false;if(word_index
==word
.size()-1&&board
[y
][x
]==word
[word_index
]) return true;_used
[y
][x
] = true;bool _t
= dfs(board
,word
,word_index
+1,x
+1,y
)||dfs(board
,word
,word_index
+1,x
,y
+1)||dfs(board
,word
,word_index
+1,x
,y
-1)||dfs(board
,word
,word_index
+1,x
-1,y
);_used
[y
][x
] = false;return _t
;}bool exist(vector
<vector
<char>>& board
, string word
) {int len1
= board
.size();int len2
= board
[0].size();unordered_set
<char> _hash
;for(auto &vec
:board
)for(auto &it
:vec
)_hash
.insert(it
);for(auto &it
:word
)if(_hash
.find(it
)==_hash
.end())return false;_used
=vector
<vector
<bool>>(len1
,vector
<bool>(len2
,false));for(int i
=0;i
<len1
;i
++){for(int j
=0;j
<len2
;j
++){if(dfs(board
,word
,0,j
,i
))return true;}}return false;}
};
4、回溯應用 - floodfill算法 問題
200. 島嶼數量
class Solution {
public:vector
<vector
<bool>> _map
;int dfs(vector
<vector
<char>>& grid
,int x
,int y
){if(x
<0||y
<0||x
>=grid
.size()||y
>=grid
.back().size()) return 0;if(grid
[x
][y
] == '0') return 0;if(_map
[x
][y
]) return 0;_map
[x
][y
] = true;return dfs(grid
,x
,y
+1)+dfs(grid
,x
+1,y
)+dfs(grid
,x
,y
)+dfs(grid
,x
-1,y
)+dfs(grid
,x
,y
-1)+1;}int numIslands(vector
<vector
<char>>& grid
) {int res
= 0;_map
= vector
<vector
<bool>>(grid
.size(),vector
<bool>(grid
[0].size(),false));for(int i
=0;i
<grid
.size();i
++)for(int j
=0;j
<grid
.back().size();j
++)if(dfs(grid
,i
,j
)) res
++;return res
;}
};
130. 被圍繞的區域
- 標準 floodfill ;思維反向一下;從外部開始dfs
class Solution {
public:
vector
<vector
<bool>> _map
;void dfs(vector
<vector
<char>>& board
, int x
, int y
){if (x
< 0 || y
< 0 || x
>= board
.size() || y
>= board
.back().size()) return ;if (board
[x
][y
] == 'X'||_map
[x
][y
]) return ;_map
[x
][y
] = true;dfs(board
,x
,y
+1);dfs(board
,x
+1,y
);dfs(board
,x
,y
-1);dfs(board
,x
-1,y
);}void solve(vector
<vector
<char>>& board
) {int len
= board
.size();int len2
= board
.back().size();_map
= vector
<vector
<bool>>(len
, vector
<bool>(len2
, false));for(int i
=0;i
<len
;i
++){if(board
[i
][0] =='O')dfs(board
,i
,0);if(board
[i
][len2
-1] =='O')dfs(board
,i
,len2
-1);}for(int i
=0;i
<len2
;i
++){if(board
[0][i
] =='O')dfs(board
,0,i
);if(board
[len
-1][i
] =='O')dfs(board
,len
-1,i
);}for(int i
=1;i
<len
-1;i
++)for(int j
=1;j
<len2
-1;j
++){if(board
[i
][j
] =='O'&&_map
[i
][j
] !=1)board
[i
][j
] ='X';}}
};
417. 太平洋大西洋水流問題 //***
class Solution {
public:int dir
;int len
;int len2
;vector
<vector
<bool>> used
;bool dfs(vector
<vector
<int>>& heights
,int x
,int y
,vector
<vector
<bool>> &_map
,int temp
){if(dir
==-1){if(x
<0||y
<0) return true;if(x
>=len
||y
>=len2
) return false;}else{if(x
<0||y
<0) return false;if(x
>=len
||y
>=len2
) return true;}if(temp
< heights
[x
][y
]) return false;if(used
[x
][y
]) return _map
[x
][y
];used
[x
][y
] = true;_map
[x
][y
] =dfs(heights
, x
- 1, y
, _map
,heights
[x
][y
])||dfs(heights
, x
, y
- 1, _map
,heights
[x
][y
])||dfs(heights
, x
+ 1, y
, _map
,heights
[x
][y
])||dfs(heights
, x
, y
+ 1, _map
,heights
[x
][y
]);used
[x
][y
] = false;return _map
[x
][y
];}vector
<vector
<int>> pacificAtlantic(vector
<vector
<int>>& heights
) {len
= heights
.size();len2
= heights
.back().size();vector
<vector
<bool>> _map(len
,vector
<bool>(len2
,false));vector
<vector
<bool>> _map2(len
,vector
<bool>(len2
,false));used
= vector
<vector
<bool>>(len
,vector
<bool>(len2
,false));vector
<vector
<int>> res
;dir
= -1;for(int i
=0;i
<len
;i
++)for(int j
=0;j
<len2
;j
++){dfs(heights
,i
,j
,_map
,heights
[i
][j
]);}dir
= 1;for(int i
=len
-1;i
>=0;i
--)for(int j
= len2
-1;j
>=0;j
--){dfs(heights
,i
,j
,_map2
,heights
[i
][j
]);}for(int i
=0;i
<len
;i
++)for(int j
=0;j
<len2
;j
++){if(_map
[i
][j
] ==true &&_map2
[i
][j
] ==true )res
.push_back({i
,j
});}return res
;}
};
- 應該從邊緣往內dfs；和上一題一樣；簡單很多 ;時間快很多
class Solution {
public:
int len
,len2
;vector
<vector
<int>> dir
= {{0,1},{1,0},{0,-1},{-1,0}};bool _fit(int &x
,int y
){if(x
<0||y
<0||x
>=len
||y
>=len2
) return false;return true;}void dfs(vector
<vector
<int>>& heights
,int x
,int y
,vector
<vector
<bool>>& _map
){if(_map
[x
][y
]) return;_map
[x
][y
] = true;for(int i
=0;i
<4;i
++){int new_x
= x
+dir
[i
][0];int new_y
= y
+dir
[i
][1];if(_fit(new_x
,new_y
) && heights
[x
][y
]<=heights
[new_x
][new_y
])dfs(heights
,new_x
,new_y
,_map
);}}vector
<vector
<int>> pacificAtlantic(vector
<vector
<int>>& heights
) {len
= heights
.size();len2
= heights
.back().size();vector
<vector
<bool>>_map1(len
,vector
<bool>(len2
,false));vector
<vector
<bool>>_map2(len
,vector
<bool>(len2
,false));vector
<vector
<int>> res
;for(int i
=0;i
<len
;i
++){dfs(heights
,i
,0,_map1
);dfs(heights
,i
,len2
-1,_map2
);}for(int i
=0;i
<len2
;i
++){dfs(heights
,0,i
,_map1
);dfs(heights
,len
-1,i
,_map2
);}for(int i
=0;i
<len
;i
++)for(int j
=0;j
<len2
;j
++)if(_map1
[i
][j
] ==true &&_map2
[i
][j
] ==true )res
.push_back({i
,j
});return res
;}
};
4、回溯應用 - 搜索問題 - 八皇后
51. N 皇后 同 面試題 08.12. 八皇后 //***這個思路牛逼啊
- 其實就是枚舉每一行中皇后應該擺在哪里，然后有一定的剪枝；
- 考慮 回溯；難點在于剪枝的判斷;
- 這里判重剪枝的方法：用三個數組；依次表示所有列，所有右上到左下對角線，所有左上到右下對角線；
class Solution {
public:vector
<vector
<string
>> res
;vector
<bool> v_used
;vector
<bool> l_used
;vector
<bool> r_used
;int _n
;void dfs(int x
,int y
,vector
<string
>& temp
){if(v_used
[y
]) return;if(l_used
[x
+y
]) return;if(r_used
[x
-y
+_n
-1]) return;v_used
[y
] = true;l_used
[x
+y
] = true;r_used
[x
-y
+_n
-1] = true;temp
[x
][y
] = 'Q';if(x
== _n
-1)res
.push_back(temp
);elsefor(int i
=0;i
<_n
;i
++)dfs(x
+1,i
,temp
);v_used
[y
] = false;l_used
[x
+y
] = false;r_used
[x
-y
+_n
-1] = false;temp
[x
][y
] = '.';}vector
<vector
<string
>> solveNQueens(int n
) {string
str_(n
,'.');vector
<string
> temp(n
,str_
);_n
= n
;v_used
= vector
<bool> (n
,false);l_used
= vector
<bool> (2*n
-1,false); r_used
= vector
<bool> (2*n
-1,false); for(int i
=0;i
<n
;i
++)dfs(0,i
,temp
);return res
;}
};
52. N皇后 II
class Solution {
public:int column_
;int l_
;int r_
;int res
;void dfs(int x
,int y
,const int& n
){if(column_
& (1<<y
)) return;if(l_
& (1<<(x
+y
))) return;if(r_
& (1<<(x
-y
+n
-1))) return;column_
|= (1<<y
);l_
|= 1<<(x
+y
);r_
|= 1<<(x
-y
+n
-1);if(x
==n
-1)res
++;elsefor(int i
=0;i
<n
;i
++)dfs(x
+1,i
,n
);column_
^= (1<<y
);l_
^= 1<<(x
+y
);r_
^= 1<<(x
-y
+n
-1);}int totalNQueens(int n
) {column_
= 0;l_
= 0;r_
= 0;res
= 0;for(int i
=0;i
<n
;i
++)dfs(0,i
,n
);return res
;}
};
37. 解數獨
class Solution {
public:int n
;vector
<int> _block
;vector
<int> _co
;vector
<int> _ro
;int which_block(const int& i
, const int& j
){if (i
< 3){if (j
< 3)return 0;else if (j
< 6)return 3;elsereturn 6;}else if (i
< 6){if (j
< 3)return 1;else if (j
< 6)return 4;elsereturn 7;}else{if (j
< 3)return 2;else if (j
< 6)return 5;elsereturn 8;}}bool dfs(int x
, int y
, int val
, vector
<vector
<char>>& board
){if (board
[x
][y
] != '.') return false;if (_ro
[x
] & (1 << val
)) return false;if (_co
[y
] & (1 << val
)) return false;if (_block
[which_block(x
, y
)] & (1 << val
)) return false;_ro
[x
] |= (1 << val
);_co
[y
] |= (1 << val
);_block
[which_block(x
, y
)] |= (1 << val
);board
[x
][y
] = val
+ '0';int begin_i
= -1, begin_j
= -1;for (int i
= x
; i
< n
; i
++){for (int j
= 0; j
< n
; j
++)if (board
[i
][j
] == '.'){begin_i
= i
;begin_j
= j
;break;}if (begin_i
!= -1)break;}if (begin_i
== -1)return true;for (int i
= 1; i
<= n
; i
++)if (dfs(begin_i
, begin_j
, i
, board
))return true;_ro
[x
] &= ~(1 << val
);_co
[y
] &= ~(1 << val
);_block
[which_block(x
, y
)] &= ~(1 << val
);board
[x
][y
] = '.';return false;}void solveSudoku(vector
<vector
<char>>& board
) {n
= 9;_block
= vector
<int>(n
, 0);_co
= vector
<int>(n
, 0);_ro
= vector
<int>(n
, 0);for (int i
= 0; i
< n
; i
++){for (int j
= 0; j
< n
; j
++){if (board
[i
][j
] != '.'){int temp
= board
[i
][j
] - '0';_ro
[i
] |= (1 << temp
);_co
[j
] |= (1 << temp
);_block
[which_block(i
, j
)] |= (1 << temp
);}}}int begin_i
= -1, begin_j
= -1;for (int i
= 0; i
< n
; i
++){for (int j
= 0; j
< n
; j
++)if (board
[i
][j
] == '.'){begin_i
= i
;begin_j
= j
;break;}if (begin_i
!= -1)break;}for (int i
= 1; i
<= n
; i
++)if (dfs(begin_i
, begin_j
, i
, board
))return;}
};
參考
【學習筆記】【C++】【Leetcode 分門別類講解】
總結
以上是生活随笔為你收集整理的【C++】【学习笔记】【递归与回溯问题详解与例题】排列问题；组合问题；二维平面回溯；flood fill问题；搜索问题（八皇后）；的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
