力扣（39.40）补9.20-创新互联

目前打算刷些算法题，数据结构的题暂时放一放吧。

39.组合总和

不会，毕竟好久没做回溯了。

看了这个图会好理解很多呦。

class Solution {

  List>ans=new ArrayList<>();

  Listlist=new ArrayList<>();

  public List>combinationSum(int[] candidates, int target) {       

  int n=candidates.length;

  Arrays.sort(candidates);

  back(candidates,target,0,n,0);

  return ans;

  }

  public void back(int[] candidates,int target,int index,int n,int sum){

  

  if(sum==target){

  ans.add(new ArrayList<>(list));

这里要对list转型才能调用add函数。

  return ;

  }

  for(int i=index;i

  

  if(sum+candidates[i]>target) break;

  else{

  list.add(candidates[i]);

  back(candidates,target,i,n,sum+candidates[i]);

  list.remove(list.size()-1);

  }

  }

  }

}

40.组合总和Ⅱ

可以做，这题和上题比，有个细节就是解集不能包含重复元素。

class Solution {

  List>ans=new ArrayList<>();

  Listlist=new ArrayList<>();

  public void back(int[] candidates,int index,int target){

  if(0==target){

  ans.add(new ArrayList<>(list));

  return;

  }

  for(int i=index;i

  if(i>index&&candidates[i]==candidates[i-1])

  continue;

这样就能保证没有重复解集。

  if(0>target)break;

  list.add(candidates[i]);

  back(candidates,i+1,target-candidates[i]);

  list.remove(list.size()-1);

  }

  }

  public List>combinationSum2(int[] candidates, int target) {

  Arrays.sort(candidates);

  back(candidates,0,target);

  return ans;

  }

}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧