题目:
给定一个无重复元素的数组 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]
]
提示:1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500
解题分析:
这种题目其实有一个通用的解法,就是回溯法。网上也有大神给出了这种回溯法解题的[通用写法](https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)),这里的所有的解法使用通用方法解答。 除了这道题目还有很多其他题目可以用这种通用解法,具体的题目见后方相关题目部分。
关键点:回溯法、backtrack 解题公式
public class CombinationSum {
public List<List<Integer>> combinationSum(int candidates[], int target){
// 创建结果集合
ArrayList<List<Integer>> result = new ArrayList<>();
// 对数组进行排序
Arrays.sort(candidates);
// 回溯
backTrack(result, new ArrayList<>(), candidates, target,0);
return result;
}
public void backTrack(List<List<Integer>> result, // 结果
List<Integer> tempList, // 另一个解
int[] candidates, // 数组
int target, // 解
int start){ // 当前递归的位置
if(target < 0) return;
else if(target == 0) result.add(new ArrayList<>(tempList));
else {
for(int i = start; i < candidates.length; i ++){
tempList.add(candidates[i]);
backTrack(result, tempList, candidates, target - candidates[i], i);
tempList.remove(tempList.size() - 1);
}
}
}
}