Combination Sum
1/22/2018
The provided array has no duplicate, so no need to remove duplicate. The solution set won't have duplicates as the tree expands.
Solution:
--------------------------------------------------------------------------------------------------------------------------
思路:
本身答案允许重复的数,让candidates里面还有重复的话,那么结果里面肯定会有重复的组合。所以要有如下代码去重复。
The provided array has no duplicate, so no need to remove duplicate. The solution set won't have duplicates as the tree expands.
Solution:
class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { // write your code here List<List<Integer>> res=new ArrayList<>(); if(candidates==null) { return null; } //Arrays.sort(candidates); List<Integer> subset=new ArrayList<Integer>(); Arrays.sort(candidates); search(subset, 0, res, candidates, target); return res; } private void search(List<Integer> subset, int startIndex, List<List<Integer>> res, int[] candidates, int remain) { if (remain == 0) { res.add(new ArrayList<>(subset)); return; } for (int i = startIndex; i < candidates.length; i++) { if (candidates[i] > remain) return; subset.add(candidates[i]); search(subset, i, res, candidates, remain - candidates[i]); subset.remove(subset.size() - 1); } } }
--------------------------------------------------------------------------------------------------------------------------
思路:
subsets的马甲。允许重复,所以startIndex是从i开始而不是i+1。
递归返回条件是target == 0, 每一次递归用target - candidates[i]。还有一种情况是target < candidates[i],需要剔除掉。
本身答案允许重复的数,让candidates里面还有重复的话,那么结果里面肯定会有重复的组合。所以要有如下代码去重复。
if (i != 0 && candidates[i] == candidates[i - 1]) {
continue;
}
评论
发表评论