首页 > 代码库 > DFS template and summary
DFS template and summary
最近一直在学习Deep Frist Search，也在leetcode上解了不少的题目。从最开始的懵懂，到现在基本上遇到一个问题有了思路。我现在还清晰的接的今年2月份我刚开始刷提的时候做subsets时那个吃力的劲，脑子就是转不过来到底该如何的递归。
void DFS_no_return(vector<TYPE>& solution_set, TYPE& solution, int idx){ // DFS terminate condition // Normally there are two major categories // One is for some number, already reach this depth according to the question, stop // get to the end of an array, stop if(idx == n || idx == (vector/string).size()){ solution_set.push_back(solution); return; } // very seldom only when our program met some efficiency problem // do prune to reduce the workload // no need do DFS if we already get the value of current element, just return if(hash_table[input] != hash_table.end()){ return; } for(int i = 0; i < n; i++){ if(visited[i] == 0){ visited[i] = 1; DFS_no_return(solution_set, solution, idx + 1); visited[i] = 0; } } return;}
对于有返回值的DFS来说。
TYPE DFS_with_return(int idx){ // DFS terminate condition // Normally there are two major categories // One is for some number, already reach this depth according to the question, stop // get to the end of an array, stop if(idx == n || idx == (vector/string).size()){ return 1/0/""; } // very seldom only when our program met some efficiency problem // do prune to reduce the workload // no need do DFS if we already get the value of current element, just return if(hash_table[input] != hash_table.end()){ return hash_table[input]; } TYPE ans; for(int i = 0; i < n; i++){ if(visited[i] == 0){ // normally, here should to add/concatenate the value in current level with the value returned from lower level ans += DFS_no_return(idx + 1); } } // if we need prune // keep current value here hash_table[input] = ans; return ans;}
总结：
DFS template and summary
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。