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.
For example, given candidate set 2,3,6,7 and target 7, A solution set is: [7] [2, 2, 3]
Have you met this question in a real interview? Yes Example given candidate set 2,3,6,7 and target 7, A solution set is: [7] [2, 2, 3]
Note - 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.
题解
和 Permutations 十分类似,区别在于剪枝函数不同。这里允许一个元素被多次使用,故递归时传入的索引值不自增,而是由 for 循环改变。
publicclassSolution { /** * @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) { List<List<Integer>> result = newArrayList<List<Integer>>(); List<Integer> list = newArrayList<Integer>(); if (candidates == null) return result;