每日一题-DFS

目录

组合总和

全排列

组合总和

• 时间：0727
• 题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

• 思路
  • 通过深度遍历的方式，找到满足条件的总和
  • 当满足的时候，开始回溯，再从新的分支继续找，回溯的时候一定要记得状态重置
  • ️  dfs向下遍历的时候，下标要用循环中的i而不是begin，如果用begin的话，会导致前面的数字会重复遍历并错误使用
• 代码

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates == null || candidates.length <= 0)
            return null;
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> sb = new LinkedList<>();
        dfs(candidates, 0, target, res, sb);
        return res;
    }
    private void dfs(int[] candidates, int begin, int target, List<List<Integer>> res, LinkedList<Integer> sb){
        if(target < 0)
            return;
        if(target == 0){
            res.add(new ArrayList<>(sb));
            begin += 2;
            return;
        }
        for(int i = begin; i < candidates.length; i ++){
            sb.addLast(candidates[i]);
            //这里一定要是i，如果是begin的话，就会造成重复查找
            dfs(candidates, i, target - candidates[i], res, sb);
            sb.removeLast();
        }
    }
}

全排列

• 时间：0729
• 题目

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

• 思路
  • 这个题目是找到所有可能的排列组合，组合内的数字不能重复出现，这就要求有一个数组记录状态
  • 这个题和上面的题目除了满足的目标条件不一样，还有一点就是上面的题目是要找等于目标值的子数组，前面的数字用过了就不需要二次访问了；但是本题全排列，每个数字都需要出现在所有的结果子集里面，所以就不需要记录当前已经访问到哪个下标了。
• 代码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0)
            return res;
        LinkedList<Integer> list = new LinkedList<>();
        // 用来存储已经访问过的元素
        boolean[] used = new boolean[nums.length];
        dfs(nums, res, list, used);
        return res;
    }
    private void dfs(int[] nums, List<List<Integer>> res, LinkedList<Integer> list, boolean[] used){
        if(list.size() == nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i < nums.length; i ++){
            if(used[i])
                continue;
            list.addLast(nums[i]);
            used[i] = true;
            dfs(nums, res, list, used);
            used[i] = false;
            list.removeLast();
        }
    }
}