Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Notice
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
Example
Given candidate set [2,3,6,7] and target 7, a solution set is:
[7]
[2, 2, 3]
思路
要求所有的解,我们用DFS。
先排个序,然后开始找。
由于一个数可以出现多次,所以往下一层搜的时候,startIndex还是设置在i。
但是注意还是需要判断,如果有两个x,第一个x如果没有被选,我们不能选第二个x。
Code
public class Solution { /** * @param candidates: A list of integers * @param target:An integer * @return: A list of lists of integers */ public List<List<Integer>> combinationSum(int[] candidates, int target) { // write your code here List<List<Integer>> res = new ArrayList<>(); if (candidates == null || candidates.length == 0) { return res; } Arrays.sort(candidates); List<Integer> list = new ArrayList<>(); helper(candidates, res, list, target, 0); return res; } public void helper(int[] candidates, List<List<Integer>> res, List<Integer> list, int target, int startIndex) { if (target == 0) { res.add(new ArrayList<Integer>(list)); return; } for (int i = startIndex; i < candidates.length; i++) { if (i != startIndex && candidates[i] == candidates[i - 1]) { continue; } if (target < candidates[i]) { break; } list.add(candidates[i]); helper(candidates, res, list, target - candidates[i], i); list.remove(list.size() - 1); } } }