https://leetcode.cn/problems/combination-sum/description/
两种搜索思路
一种是选或不选,搜索树是一颗二叉树
另一种是选哪个数,是一个n叉树
二叉
class Solution {
List<List<Integer>> res = new ArrayList<>();
int target;
int[] nums;
List<Integer> path= new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
this.nums=candidates;
this.target=target;
dfs(0,0);
return res;
}
void dfs(int step,int sum)
{
if(step>=nums.length || sum>target)return;
if(sum==target)
{
res.add(new ArrayList(path));
return;
}
// 不选
dfs(step+1,sum);
// 选
path.add(nums[step]);
dfs(step,sum+nums[step]);
path.remove(path.size()-1);
}
}
n叉
class Solution {
List<List<Integer>> res = new ArrayList<>();
int target;
int[] nums;
List<Integer> path= new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
this.nums=candidates;
this.target=target;
dfs(0,0);
return res;
}
void dfs(int startNum,int sum)
{
if(sum>target)return;
if(sum==target)
{
res.add(new ArrayList(path));
return;
}
// 多分支
for(int i=startNum;i<=nums.length-1;i++)
{
path.add(nums[i]);
dfs(i,sum+nums[i]);
path.remove(path.size()-1);
}
}
}
标签:39,target,nums,int,res,sum,path,leetcode,总和 From: https://www.cnblogs.com/lxl-233/p/18194867