leetcode39-组合总和

彭晨涛 • 2020年5月1日 13:20 • 算法 • 阅读 269

原题

给定一个无重复元素的数组 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查找，如果画出树状图的话，会看到这个搜索树因为某些部分条件不满足，于是不再向下查找，称为“剪枝”。

那么其他题解说的“回溯算法”是什么呢，其实用递归实现的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/

leetcode39-组合总和

原题

解法

思想

代码

相关推荐

发表回复