leetcode之组合数(Combination Sum)

本文主要是介绍leetcode之组合数(Combination Sum)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Combination Sum

//代码1
public class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<List<Integer>>();if(candidates.length == 0 || candidates == null) return result;Arrays.sort(candidates);List<Integer> list = new ArrayList<Integer>();helper(result, list, candidates, 0, target);return result;}private void helper(List<List<Integer>> result,List<Integer> list,int[] candidates,int sum,int target) {if(sum == target) {result.add(new ArrayList<Integer>(list));return;}for(int i = 0; i < candidates.length; i++) {//每层的循环都是从0开始，导致出现重复的组合if(sum + candidates[i] <= target) {list.add(candidates[i]);helper(result, list, candidates, sum + candidates[i], target);list.remove(list.size() - 1);}elsebreak;}}
}

Your answer：[[2,2,3],[2,3,2],[3,2,2],[7]]
Expected answer：[[2,2,3],[7]]

//代码2
public class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<List<Integer>>();if(candidates.length == 0 || candidates == null) return result;Arrays.sort(candidates);List<Integer> list = new ArrayList<Integer>();helper(result, list, candidates, target, 0);return result;}private void helper(List<List<Integer>> result,List<Integer> list,int[] candidates,int target,int k) {if(target == 0) {result.add(new ArrayList<Integer>(list));return;}if(target > 0) {for(int i = k; i < candidates.length; i++) {if(target < candidates[i]) break;list.add(candidates[i]);helper(result, list, candidates, target - candidates[i], i);//两处修改的地方list.remove(list.size() - 1);}}}
}

正解代码2对代码1做了2点优化：

1. 每层循环从当前开始层数开始，防止出现重复组合；
2. 传入的参数由和改为差值，这样可防止在数值很大的情况下出现溢出的异常。

Combination Sum II

在回溯法中，如果要去除重复的元素，只需在for循环中加入一个条件判断即可，这个条件判断隐含了两层意思：
1. 每一层的第一个元素无条件加入解空间树
2. 这一层从第二个元素开始进行比较，若这个元素与前面元素相同，不应该加入解空间树

public class Solution {public List<List<Integer>> combinationSum2(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<List<Integer>>();if(candidates.length == 0 || candidates == null) return result;Arrays.sort(candidates);List<Integer> list = new ArrayList<Integer>();helper(result, list, candidates, target, 0);return result;}private void helper(List<List<Integer>> result,List<Integer> list,int[] candidates,int target,int k) {if(target == 0) {result.add(new ArrayList<Integer>(list));return;}if(target > 0) {for(int i = k; i < candidates.length; i++) {if(target < candidates[i]) break;if(i > k && candidates[i] == candidates[i - 1]) continue;//多个一个判断条件list.add(candidates[i]);helper(result, list, candidates, target - candidates[i], i + 1);//在代码2中，这里是ilist.remove(list.size() - 1);}}}
}

这篇关于leetcode之组合数(Combination Sum)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---