39、组合总和
给定一个无重复元素的数组 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：递归回溯，深度优先
class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);// 排好序，方便回溯
getAllAnswer(candidates,0,new Stack<>(),target);
return ans;
}
// 递归 回溯 结合图形编码
private void getAllAnswer(int[] can,int index,Stack<Integer> res,int target) {
if (0 == target) {
List<Integer> ans0 = new ArrayList<Integer>(res);
ans.add(ans0);
return;
}
// 剪枝 target - can[i] >= 0
for (int i = index;i < can.length && target - can[i] >= 0;i++) {
res.add(can[i]);
getAllAnswer(can,i,res,target-can[i]);// 递归
res.pop();// 回溯，利用栈的特性，将最后入栈的元素出栈
}
}
}
解法2：动态规划
- 求出1-target的所有解
// 由@liu-li-8提供
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Map<Integer,Set<List<Integer>>> map = new HashMap<>();
//对candidates数组进行排序
Arrays.sort(candidates);
int len = candidates.length;
// 逐渐增加目标值
for(int i = 1;i <= target;i++){
//初始化map
map.put(i,new HashSet<>());
//对candidates数组进行循环
for(int j = 0;j < len&&candidates[j] <= target;j++){
// 目标值已存在
if(i == candidates[j]){
//相等即为相减为0的情况，直接加入set集合即可
List<Integer> temp = new ArrayList<>();
temp.add(i);
map.get(i).add(temp);
}else if(i > candidates[j]){// 目标值
//i-candidates[j]是map的key
int key = i-candidates[j];
//使用迭代器对对应key的set集合进行遍历
//如果candidates数组不包含这个key值，对应的set集合会为空，故这里不需要做单独判断
for(Iterator iterator = map.get(key).iterator();iterator.hasNext();){
List list = (List) iterator.next();
//set集合里面的每一个list都要加入candidates[j]，然后放入到以i为key的集合中
List tempList = new ArrayList<>();
tempList.addAll(list);
tempList.add(candidates[j]);
//排序是为了通过set集合去重
Collections.sort(tempList);
map.get(i).add(tempList);
}
}
}
}
result.addAll(map.get(target));
return result;
}
}
// 作者：chun-meng-da-xiao-yang
// 链接：https://leetcode-cn.com/problems/combination-sum/solution/chao-qiang-gifzhu-ni-shi-yong-dong-tai-gui-hua-qiu/
40、组合总和II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
- 说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
- 输入:
candidates = [10,1,2,7,6,1,5], target = 8, - 所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
- 输入:
candidates = [2,5,2,1,2], target = 5, - 所求解集为:
[
[1,2,2],
[5]
]
递归回溯，删除重复元素
// 解法 1，稍微修改一下上一题的代码
class Solution {
Set<List<Integer>> ans = new HashSet<List<Integer>>();// 利用Set去重
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// 数组有重复元素，每个元素只能使用一次
Arrays.sort(candidates);// 排好序，方便回溯
getAllAnswer(candidates,0,new Stack<>(),target);
return new ArrayList<List<Integer>>(ans);// 这里比较耗时
}
// 递归 回溯 结合图形编码
private void getAllAnswer(int[] can,int index,Stack<Integer> res,int target) {
if (0 == target) {
List<Integer> ans0 = new ArrayList<Integer>(res);
ans.add(ans0);
return;
}
// 剪枝 target - can[i] >= 0
for (int i = index;i < can.length && target - can[i] >= 0;i++) {
res.add(can[i]);
getAllAnswer(can,i+1,res,target-can[i]);// 递归。i+1每个元素智能使用一次
res.pop();// 回溯，利用栈的特性，将最后入栈的元素出栈
}
}
}
// 优化一下
class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// 数组有重复元素，每个元素只能使用一次
Arrays.sort(candidates);// 排好序，方便回溯
getAllAnswer(candidates,0,new Stack<>(),target);
return ans;
}
// 递归 回溯 结合图形编码
private void getAllAnswer(int[] can,int index,Stack<Integer> res,int target) {
if (0 == target) {
List<Integer> ans0 = new ArrayList<Integer>(res);
ans.add(ans0);
return;
}
// 剪枝 target - can[i] >= 0
for (int i = index;i < can.length && target - can[i] >= 0;i++) {
if(i > index && can[i] == can[i-1]) continue;// can[i]加入结果，从index + 1 开始去重
res.add(can[i]);
getAllAnswer(can,i+1,res,target-can[i]);// 递归
res.pop();// 回溯，利用栈的特性，将最后入栈的元素出栈
}
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
