dfs经典问题

dfs的题实际就是穷举，递归调用函数，需要注意的是函数出口的设置和状态的回退

leetcode22 括号生成

class Solution {
    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        dfs(n,"",0,0);
        return res;
    }
    public void dfs(int n,String temp,int left,int right){
        if(left>n||right>left){
            return;
        }

        if(left==n &&right==n){
            res.add(new String(temp));
        }

        dfs(n,temp+'(',left+1,right);
        dfs(n,temp+')',left,right+1);
    }
}

leetcode39 组合总和

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> temp = new ArrayList<>();
        dfs(candidates,temp,0,0,target);
        return res;
    }

    public void dfs(int[] candidates,List<Integer> temp,int index,int sum,int target){
        if(sum > target){
            return;
        }else if(sum == target){
            res.add(new ArrayList<>(temp));
            return;
        }

        for(int i=index;i<candidates.length;i++){
            temp.add(candidates[i]);
            dfs(candidates,temp,i,sum+candidates[i],target);
            temp.remove(temp.size()-1);
        }
    }
}

leetcode40 组合总和II

class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<Integer> temp = new ArrayList<>();
        dfs(temp,candidates,target,0,0);
        return res;
    }

    public void dfs(List<Integer> temp,int[] candidates,int target,int index,int sum){
        if(sum > target){
            return;
        }
        if(sum == target){
            res.add(new ArrayList<>(temp));
            return;
        }
        for(int i=index;i<candidates.length;i++){
            /* 这题 i>index 的判断是精髓 */
            if(i>index && candidates[i] == candidates[i-1]){
                continue;
            }
            temp.add(candidates[i]);
            dfs(temp,candidates,target,i+1,sum+candidates[i]);
            temp.remove(temp.size()-1);
        }
    }
}

leetcode47 全排列II

class Solution {

    List<List<Integer>> res=new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> temp=new ArrayList<>();
        boolean[] flag=new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums,flag,temp);
        return res; 
    }

    public void dfs(int[] nums,boolean[] flag,List<Integer> temp){
        if(temp.size()==nums.length){
            res.add(new ArrayList<>(temp));
            return ;
        }

        for(int i=0;i<nums.length;i++){
            if(flag[i]){
                continue;
            }
            /** !flag[i-1] 是为了限制相同数字的访问顺序只能有一种 */
            if(i>=1&&nums[i]==nums[i-1]&&!flag[i-1]){
                continue;
            }
            temp.add(nums[i]);
            flag[i]=true;
            dfs(nums,flag,temp);
            temp.remove(temp.size()-1);
            flag[i]=false;
        }
    }
}

leetcode113 路径总和II

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<Integer> temp=new ArrayList<>();
        dfs(root,targetSum,0,temp);
        return res;
    }

    public void dfs(TreeNode root,int targetSum,int sum,List<Integer> temp){
        if(root==null){
            return;
        }
        temp.add(root.val);
        if(sum+root.val==targetSum&&root.left==null&&root.right==null){
            res.add(new ArrayList<>(temp));
        }
        dfs(root.left,targetSum,sum+root.val,temp);
        dfs(root.right,targetSum,sum+root.val,temp);
        temp.remove(temp.size()-1);
    }

}