dfs算法的leetCode实战最近磨出了不少dfs算法的问题，但目前在leetCode上遇到dfs问题很容易求解。 这里分享一下自己制作dfs算法的经验。
另一方面，对于DFS dfs，实际上是深度优先搜索算法。 本质上是递归算法的一种。 探索时沿着树的深度扫描，尽可能深入地探索树枝。
2 .具体实战我就不多谈了，但对于dfs算法的具体操作还是需要在实战中加深印象。
2.1 LeetCode39题
指定无重复元素的正整数数组candidates和正整数target，以在candidates中找到唯一可以使用数字和目标数target的组合。
candidates的数字可以无限制地重复选择。 如果至少有一个选定的数字数不同，则两个组合是唯一的。
对于给定的输入，保证和target的唯一组合数小于150。
示例1 :
输入： candidates=[ 2，3，6，7 ]，target=7输出： [[7]，[ 2，2，3 ] ]例2 :
输入： candidates=[ 2，3，5 ]，target=8输出： [ [ 2，2，2，2，2 ]，[ 2，3，3 ]，[ 3，5 ] ]示例3 :
输入： candidates=[2]，target=1输出： []例4 :
输入： candidates=[1]，target=1输出： [[1]]示例5 :
输入： candidates=[1]，target=2输出： [ [ 1，1 ] ]
对于这样的枚举主题，在很多情况下dfs可以解决这个问题。
对于dfs的主题，我们第一步是做这棵树，发现他的边界条件。
树的形状如下图所示。
为了达到目的，我们其实是一种叫dfs的树，列举所有可能的结果。 此时，需要找到递归的结束条件。
即使我做了x，也已经不能有子节点了。 因为此时你的和已经表明大于target。 往下走已经没有意义了
当等于target时，可以返回result。
如果是target或更高版本，则必须追溯到上一个节点，并遵循另一个分支。 例如，你遍历了2，2，6，sum=10target。 此时，需要追溯到22这个节点。 所以，此时需要重新设定result和sum的值。
我们开始写代码了
privatestaticlistlistintegercombinationsum (int [ ] candidates，int target ) ) listlistintegerresultlist=new ArrayList； df s39 (结果列表，新阵列)，0，target，candidates )； 返回结果列表； } privatestaticvoiddfs 39 (listlistinteger result list，listintegerresult，int sum，int target，int[] candidates ) /退出条件ii collections.sort(copyresult； if (！ resultlist.contains(copyresult ) (resultlist.add ) (copyresult )； } return； //候选节点for (int candidate : candidates ) { sum =candidate； result.add(candidate；//执行dfsdf s39 (结果列表、结果、sum、target、candidates )； //在追溯到sum-=result.get(result.size(-1 )； result.remove(result.size ) (- 1 )； }} 2.2 LeetCode22题
n表示要生成括号的对数。 请设计一个可以生成所有可能的括号组合的函数。
有效的括号组合必须以正确的顺序封闭左括号。
示例1 :
输入： n=3
输出(() () ) ) )、() ) ) ) ) ) ) ) ) )的输出) ) ) ) ) ) )的输出) ) ) ) ) )的输出)
示例2 :
输入： n=1
输出： [ ' () ]
这个主题也是列举类的主题，用dfs列举，如果满足条件的话追加到集合中就可以了。
1 .生成树。 生成树的图示如下。
生成树的逻辑如下。
)1)添加左括号即左子节点，添加右括号即右子节点。
2 .判断边界条件
为了便于书写，剩下的左边的数记为left； 剩下右边的数记为right；
(1) left一定小于right。 如果left还大于right的话，很明显，已经不符合题意了。
)2) left和right都不能小于0。
)3)如果left和right都为0，就是我们想要的答案。
3 .进行回溯。
dfs成功后，需要返回上一个节点。 否则，sb的值会被污染。
接下来进行代码编写。
publicclasssolutiontest { publicstaticliststringgenerateparenthesis (intn ) stringbuilder sb=new stringbuilder )； ListString result=new ArrayList (； DFS22(n-1，n，sb，result，true )； DFS22(n，n - 1，sb，result，false )； 返回结果； }私有状态标志22 (int left，int right，StringBuilder sb，ListString result，boolean leftFlag )左标志)左标志(sb ) //这个必须写在sb的后面。 追溯时if(left0) { return； (if ) right0) { return； }//如果left大于right，则返回正确的括号if(leftright ) )； (如果左和右都为0，则表示结果为if(left==0right==0) (result.add ) sb.tostring ) )。 返回； } //dfs左数据DFS22(left-1，right，sb，result，true )； sb.deletecharat(sb.length ) (- 1 )； //dfs右侧的逻辑DFS22(left，right - 1，sb，result，false )； sb.deletecharat(sb.length ) (- 1 )； }