最近一直在学习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; }
总结：
原文：http://www.cnblogs.com/wdw828/p/6840317.html