leetcode39-组合总和

原题

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

解法

本题解同步发于leetcode题解:Java DFS,让你知道组合怎么去重&剪枝&回溯到底是什么

思想

该题难点在于组合的去重,如果直接不加条件的dfs很容易找到相同的组合,例如示例一可以找出[2,2,3][2,3,2][3,2,2],它们实质上是同一个组合。如果要进行去重,可以考虑给组合添加一个限制条件,例如我们要求,找到的组合中前面的数必须大于等于后面的数。

那么为了只找到满足条件的组合,可以先将candidates数组从小到大排序,每次dfs选取一个元素之后,我们就不再选取比它大的元素(即后面只在下标小于等于它的元素中查找)。这样就可以做到查找到的组合满足前面的数总是大于等于后面的数。

这样的dfs查找,如果画出树状图的话,会看到这个搜索树因为某些部分条件不满足,于是不再向下查找,称为“剪枝”。

leetcode39-组合总和

leetcode39-组合总和

那么其他题解说的“回溯算法”是什么呢,其实用递归实现的DFS就必然会经过回溯,当条件不满足时,递归函数需要返回到上一层节点,继续查找,称为“回溯”。

代码

class Solution {
    List<List<Integer>> ans;
    int[] candidates;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ans = new ArrayList<>();
        //先对candidates从小到大排序
        Arrays.sort(candidates);
        this.candidates = candidates;
        List<Integer> list = new ArrayList<>();
        dfs(list,target,candidates.length-1);
        return ans;
    }

    //maxIndex表示允许在candidates搜索到的最大下标
    public void dfs(List<Integer> list,int target,int maxIndex){
        for(int i = 0;i<=maxIndex;i++){
            if(candidates[i]<=target){
                List<Integer> copyList = new ArrayList<>(list);
                copyList.add(candidates[i]);
                if(candidates[i]==target) {
                    ans.add(copyList);
                    return;
                }
                //当选取下标为i的节点后,下一步只允许在下标小于等于i的元素中查找
                dfs(copyList,target-candidates[i],i);
            }
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode39-%e7%bb%84%e5%90%88%e6%80%bb%e5%92%8c/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月30日
下一篇 2020年5月1日

相关推荐

  • leetcode658-找到K个最接近的元素

    原题 给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样,优先选择数值较…

    算法 2020年1月4日
    0110
  • leetcode278-第一个错误的版本

    原题 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假…

    算法 2020年1月2日
    080
  • leetcode5-最长回文子串

    原题 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有…

    算法 2020年2月20日
    0110
  • leetcode16-最接近的三数之和

    原题 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存…

    算法 2020年5月4日
    070
  • leetcode279-完全平方数

    原题 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出…

    2019年12月11日
    0120
  • leetcode26-删除排序数组中的重复项

    原题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空…

    算法 2019年11月23日
    0180
  • leetcode15-三数之和

    原题 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。 注意:…

    算法 2020年5月4日
    0150
  • leetcode77-组合

    原题 给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], […

    算法 2020年5月12日
    0540
  • leetcode887-鸡蛋掉落

    原题 你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。 你知道存在楼层 F ,满足 0 &…

    算法 2020年4月11日
    0110
  • leetcode322-零钱兑换

    原题 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 示例 1…

    算法 2020年3月8日
    0130

发表回复

登录后才能评论