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日

相关推荐

  • leetcode733-图像渲染

    原题 有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一…

    2019年12月13日
    0140
  • leetcode70-爬楼梯

    原题 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意: 给定 n 是一个正整数。  示例 1: 输入:…

    算法 2020年1月21日
    0950
  • leetcode35-搜索插入位置

    原题 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1: 输入: […

    算法 2020年3月2日
    0130
  • leetcode1431-拥有最多糖果的孩子(儿童节快乐!)

    原题 给你一个数组 candies 和一个整数 extraCandies ,其中 candies[i] 代表第 i 个孩子拥有的糖果数目。 对每一个孩子,检查是否存在一种方案,将额…

    算法 2020年6月1日
    0310
  • 剑指offer35-复杂链表的复制

    原题(来源Leetcode) 请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random …

    2020年6月13日
    0110
  • 十大排序算法与Java实现

    本文参考资源: https://github.com/iTimeTraveler/SortAlgorithms 十大经典排序算法 - 冰狼爱魔 - 博客园 十大经典排序算法总结(J…

    2020年3月11日
    0830
  • 剑指offer45-把数组排成最小的数

    原题(来源Leetcode) 输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: "102" …

    算法 2020年6月11日
    0150
  • leetcode167-两数之和II-输入有序数组

    原题 给定一个已按照 升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值index1和index2,其中index1必须小于index2。 说明…

    算法 2019年11月20日
    0200
  • leetcode347-前K个高频元素

    原题 给定一个非空的整数数组,返回其中出现频率前 k 高的元素。 示例1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例2: 输入: n…

    算法 2019年12月28日
    0170
  • leetcode498-对角线遍历

    这是一个Z字形编排问题,JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下…

    2019年11月14日
    0110

发表回复

登录后才能评论