目录
- 题目连接:39. 组合总和
1- 思路
注意如果借助 startIndex
实现,理解 startIndex
的含义
- 在本题目中,由于同一个元素可以重复选取,因此
startIndex
在传递的过程中,不需要进行+1
操作,传递的值为i
2- 实现
⭐39. 组合总和——题解思路
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backTracing(candidates, target, 0, 0);
return res;
}
// 1. 回溯参数及返回值
public void backTracing(int[] candidates, int target, int nowSum, int startIndex) {
if (nowSum > target) {
return;
}
// 2. 结束条件
if (nowSum == target) {
res.add(new ArrayList(path));
return;
}
// 回溯
for (int i = startIndex; i < candidates.length; i++) {
nowSum += candidates[i];
path.add(candidates[i]);
backTracing(candidates, target, nowSum, i);
nowSum -= candidates[i];
path.remove(path.size() - 1);
}
}
}
3- ACM 实现
public class combination {
static List<List<Integer>> res = new ArrayList<>();
static List<Integer> path = new ArrayList<>();
public static List<List<Integer>> combine(int[] candidates,int target){
// 回溯
backTracing(candidates,target,0,0);
return res;
}
public static void backTracing(int[] candidates,int target,int nowSum,int startIndex){
// 终止条件
if(nowSum>target){
return;
}
if(nowSum==target){
res.add(new ArrayList<>(path));
}
//回溯
for(int i = startIndex;i<candidates.length;i++){
nowSum += candidates[i];
path.add(candidates[i]);
backTracing(candidates,target,nowSum,i);
nowSum -= candidates[i];
path.remove(path.size()-1);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
input = input.replace("[","").replace("]","");
String[] parts = input.split(",");
int[] nums = new int[parts.length];
for(int i = 0 ; i < parts.length;i++){
nums[i] = Integer.parseInt(parts[i]);
}
System.out.println("输入target");
int target = sc.nextInt();
System.out.println("结果是"+combine(nums,target).toString());
}
}
标签:39,target,nowSum,int,new,candidates,path,Hot100,LeetCode
From: https://blog.csdn.net/weixin_44382896/article/details/141632862