深度优先遍历:
从0开始,到1,发现1只和0连接,退回到1,接着到2,再退回到1,接着到5,5和3有连接,再到3,3和4有连接,再到4,4和6有连接,再到6。最后6的相邻结点被遍历完,退回到4,3,5,0,结束。
应用:求连通分量
回溯法+深搜:
注意一定要先将candidates从小到大排序。
class Solution {public: vector> combinationSum(vector & candidates, int target) { vector > results{}; vector result{}; sort(candidates.begin(), candidates.end()); dfs(results, result, candidates, target, 0); return results; } void dfs(vector >& results, vector & result, vector & candidates, int target, int level){ if(target==0){ results.push_back(result); return; } //find for(int i=level; i =0 ; ++i){ result.push_back(candidates[i]); dfs(results, result, candidates, target-candidates[i], i); result.pop_back(); } }};