LeetCode

39(40、216)-组合总和Ⅰ、Ⅱ、Ⅲ-典型回溯问题

2020-03-21  本文已影响0人  华雨欣

题目

分析

回溯问题最简单的思想就是直接dfs暴力搜索,找出每一种情况即可,不过这样的时间效率不会很高,需要进一步的优化(剪枝)。另外,题目需要得到和为 target 的组合的集合,由于给定数组没有重复元素,故只要保证 下一次搜索的数的下标 >= 当前下标 即可避免出现重复解集。我们可以采用减法使得每次遍历到一个数就将 target 值减去遍历元素传递给更深一层,target <= 0 时递归结束返回(当然加法也同理,用一个变量记录和,和等于 target 时递归结束返回)。分析图如下:

可以得到代码如下:

class Solution {

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

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, 0, new Stack<Integer>());
        return ans;
    }

    public void dfs(int[] candidates, int target, int index, Stack<Integer> com) {
        if (target == 0) {
            ans.add(new ArrayList<Integer>(com));
        } else if (target > 0) {
            for (int i = index; i < candidates.length; i++) {
                com.push(candidates[i]);
                dfs(candidates, target - candidates[i], i, com);
                com.pop();
            }
        }
    }
}

成功AC,不过时间方面还可以再优化。

优化

通过观察分析图,可以发现,对于排好序的数组,只要小的数不满足条件,后边的元素遍都可以不用遍历了,从而可以实现剪枝,代码如下:

class Solution {

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

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //排序方便剪枝
        Arrays.sort(candidates);
        dfs(candidates, target, 0, new Stack<Integer>());
        return ans;
    }

    public void dfs(int[] candidates, int target, int index, Stack<Integer> com) {
        if (target == 0) {
            ans.add(new ArrayList<Integer>(com));
        } else if (target > 0) {
            for (int i = index; i < candidates.length; i++) {
                //数组元素比当前目标大,后边的元素都不用遍历了
                    if (target < candidates[i])
                    break;
                com.push(candidates[i]);
                dfs(candidates, target - candidates[i], i, com);
                com.pop();
            }
        }
    }
}

提交后大概3ms,比较令人满意的效率。

组合总和Ⅱ

题目如下:


分析

与第一题相比,数组包含重复元素,但是每个数字只能使用一次,这就说明,在第一题基础上,当向深层遍历的时候只能从当前的元素向后遍历(不含当前元素)。但是有重复元素,哪怕排完序也会出现重复的解集组合,不过对于下面数组示例可以发现:

排序后的数组对于重复的数字会出现重复的解,但是第一个元素(第一个1、3)不会出现重复,所以,从第一个之后跳过所有重复的数字即可,即:

/* 跳过重复的数字 */
if (i > index && candidates[i] == candidates[i - 1])
                    continue;

完整代码

class Solution {

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

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

    public void dfs(int[] candidates, int target, Stack<Integer> stack, int index) {
        if (target < 0) {
            return;
        } else if (target == 0) {
            ans.add(new ArrayList<Integer>(stack));
        } else {
            for (int i = index; i < candidates.length; i++) {
                if (candidates[i] > target) {
                    break;
                }

                if (i > index && candidates[i] == candidates[i - 1])
                    continue;
                stack.add(candidates[i]);
                dfs(candidates, target - candidates[i], stack, i + 1);
                stack.pop();
            }
        }
    }
}

整体思路与第一题没什么差别,主要是一点细节上的处理。

组合总和Ⅲ

题目如下:

第三题思路与前两题基本一致,甚至难度比前两题还要小一点,就不再讲解,给出完整代码:

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
         ArrayList<List<Integer>> ans = new ArrayList();
         dfs(k, n, ans, new Stack<Integer>(), 1);
         return ans;
    }

    public void dfs(int k, int n, ArrayList<List<Integer>> ans, Stack<Integer> stack, int start){
        if(k == 0){
            if(n == 0){
                ans.add(new ArrayList(stack));
            }
        }else{
            for(int i = start; i <= 9; i++){
                stack.push(i);
                if(i > n){
                    stack.pop();
                    break;
                }
                   
                dfs(k - 1, n - i, ans, stack, i + 1);
                stack.pop();
            }
        }
    }
}

认真总结,仔细研究,未来可期。

上一篇下一篇

猜你喜欢

热点阅读